Linear Search And Binary Search Using Python

The searching technique is one of the important topic in the data structure, this particular topic is loved by many interviewers and is asked in many competitive exams, the two of the most popular searching techniques are-:

 

1. Linear search

2. Binary search

 

These two methods of searching are widely used. We shall learn about both methods in detail using examples to showcase the working and the implementation using python programming language.

 

Linear Search

 

Linear search is the simplest way of searching for an element in a list, this searching technique is also known as sequential search. It is used to find a particular value in the list. As this technique is linear, it checks every element before the particular value we are searching for. 

 

The linear search could also be treated as a special case of brute force searching. The worst case of the linear search will be when the element or value we need to find is at the last, therefore the worst case of linear search is directly proportional to the number of elements in the list.

 

(Must read: A Python Tutorial on Partition and QuickSort Algorithm)

 

Let’s examine the working of linear search. The concept is very simple, initially, the algorithm will start from the first element and will check if that element matches the element we want or not, if it matches, then we shall return the index, otherwise check the next element.

Let us suppose we need to search for ‘14’ in the given list, we will declare a variable ‘i’ that will check if the first value is ‘14’ or not, the first value here is ‘9’, therefore it will continue its search and move to the next value.

The next element is ‘15’, which is not equal to our target element, again it will continue its search and move to the next element, which is ‘7’.

‘7’ is not equal to our target element, again it will move further to search for ‘14’, the next element is ‘11’.

As ‘11’ is also not equal to our target element, the variable will continue its search without stopping, the next element is ‘14’, which is equal to the target variable, and this is what we were searching for, therefore, we shall stop here.

Our search will end here, and we will return the index of the target element, if we start from 0, then the index of ‘14’ will be 4, therefore, ‘4’ will be returned.

 

Linear Search Python Program

---

ar = [10,7,1,3,-4,2,20]

x = len(ar)

 

def LS(ar,TE):

    for i in range(x):

        if ar[i]==TE:

            return i

    return 'not present'

---

The python code for the linear search is written above, a list with the variable name ‘ar’ is assigned whereas variable ‘x’ is used to check the length of the list, a function named ‘LS’ is defined, which takes two parameters, one the list and other parameter is target element.

 

(Also read: Python Essentials For Voice Control)

 

After we have assigned the parameters, we will form a loop where the index will start from 0 to the length of the list, then we will check whether the element in the current index is equal to our target element, if it is equal, we are returning the index, if it is not, the loop will work again. Lastly, we have returned a statement that works if the element is not present in the given list.

 

 

Binary Search

 

Binary search is another technique that is used to find a particular value or an element in a linear array, this technique is faster than the linear search as it uses a technique called ‘Divide and conquer’, using this technique, the search area is limited and is reduced by half. 

 

In binary search, all the values we find the median of the array, after that we compare that if the value at the middle index is the value we are searching for or not, if it matches, then we return the middle index, otherwise we compare if the value we are searching for is greater than the middle element if so, we will apply recursion from the adjacent index of the middle index to the rightmost or the last index. 

 

If the value is less than the element on the middle index, we will again apply the recursion from the leftmost index, i.e, the starting index to the middle - 1 index.

 

(Suggested blog: NLTK python tutorial)

 

Let’s try to understand it visually.

 

Let us say our target element is ‘45’, we will find out the middle element first, in order to do so, we will declare two variables, ‘l’ for the leftmost index and ‘r’ for the rightmost index. We will use the floor function to determine the middle index, ‘l’ is at 0th index, whereas ‘r’ is at 7th index, the middle element will be (0+7)//2 = 3. Therefore the third index or 21 is our middle element.

Now we will check if the middle element is equal to the target element, in our case, it is not, therefore we move to check whether the target element is greater than or less than the middle element, the target element is greater than the middle element in our case, therefore we will again apply binary search, but from middle + 1 to ‘r’.

Now, if we will apply binary search from mid+1 to r, the process will start over, to find the middle index, (3+7)//2 = 5, now, we shall check whether the middle element is equal to the target element, in this case it is, we will simply return the index of the middle element.

We have successfully found our element using the ‘Divide-and-conquer’ technique. 

 

Binary Search Python Program

---

a = [9,10,21,232,432,543,760,793,812,888]

def BS(a,val,l,r):

    if r<l:

        return 'element is not there'

    

    mid = (l+r)//2

    

    if a[mid]==val:

        return mid

    

    if a[mid]>val:

        return BS(a,val,l,mid-1)

        

    else:

        return BS(a,val,mid+1,r)

---

Just like the merge sort and quicksort, we are going to apply recursion to implement the program, one of the major benefits of using recursion is that it is extremely fast, one downside could be that we need refinement of data, for example, in the case of binary search, we need sorted data in order to implement recursion. 

 

In the python program, we have an array ‘a’ with 10 elements, from index 0 to 9. We have defined a function BS that takes 4 parameters, which are-: array, the target element, leftmost index, and the rightmost index. After defining the function, we will have a base case, where if the number is not present in an array, it will simply show a message that ‘element is not there’ .

 

After defining the base case, we are finding the middle index using the floor function and checking if the element at the middle index is equal to the target element or not, if yes, we are returning the index. Rest is all the same as discussed in the theory and fairly simple.

 

What is the time complexity of binary search?

 

The time complexity of a binary search algorithm for searching a value in an entire list is o(logn), as it uses the ‘divide-and-conquer’ technique, which divides the whole problem into similar sub-problems, therefore the after each step, the problem is divided into half, so this is how it goes, if the problem is of the size ‘n’, then the problem will break like, n + n/2 + n/4+.......1, which becomes o(nlogn).

 

As in any case, the problem is going to be distributed in half, that’s why the time complexity will remain the same for the best case, average case, and the worst case as well.

 

 

Conclusion

 

To conclude, we have examined the linear search algorithm with an example, the plus point of this algorithm is that it is very easy to implement and doesn’t require sorted array list, on the other hand binary search is very fast as compared to the linear search, but the list has to be sorted in order to implement binary search algorithm. 

 

(Recommended blog: Scrapy Tutorial for Web Scraping With Python)

 

The python implementation of binary search and linear search is explained with the help of this blog.