Linear & Binary Search

Linear search & Binary Search

start

index

Linear Search

Binary Search

Pros & Cons

Pros & cons

Example of linear search

Example of binary search

Code for linear search

Code for binary search

References

Linear Search

context

Linear search is a method of finding elements within a list. It is also called a sequential search. It is the simplest searching algorithm because it searches the desired element in a sequential manner. It compares each and every element with the value that we are searching for. If both are matched, the element is found, and the algorithm returns the key's index position.

Applications of Linear Search

• Used to find the desired element from the collection of data when the dataset is small
• The searching operations is less than 100 items

PROS and cons of linear search

Cons

Pros

• Slow searching of large lists.

• Simple and easy to understand and Implement

• Not suitable for large array.

• Not affected by insertions and deletions

• can be less efficient than other algorithms

• Will perform fast searches of small to medium lists.

Example of linear search in python

Let's understand the following steps to find the element key = 7 in the given list.

Step - 1: Start the search from the first element and Check key = 7 with each element of list x.

Step - 2: If element is found, return the index position of the key.

Step - 3: If element is not found, return element is not present.

CODE for linear search in python

Let's understand the following Python implementation of the linear search algorithm.

Output:

Code:

Element found at index: 4

Binary Search

context

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. The main idea of binary search is to keep track of the current range of reasonable guesses.

Applications of binary Search

• This algorithm is used to search element in a given sorted array with more efficiency.
• It could also be used for few other additional operations like- to find the smallest element in the array or to find the largest element in the array.

PROS and cons of Binary search

Cons

Pros

• Can be used only when data is sorted.

• Much quicker.

• Works on the divide and conquers principle.

• More complicated.

• If random access is not supported then efficiency might be lost.

• Efficient.

• A simple algorithm to understand.

• Can be implemented only for two-way transversal data structures.

Example of bINARY search in python

CODE for linear search in python

Let's understand the following Python implementation of the binary search algorithm.

Output:

Code:

6 Element 7 is present at index 6.

References

bibliography

• https://www.scaler.com/topics/binary-search-in-python/
• https://app.genial.ly/editor/63e060200f4f2a00192c7117
• https://www.studytonight.com/python-programs/binary-search-in-python
• https://www.javatpoint.com/binary-search-in-python
• https://www.guru99.com/binary-search.html