Binary Search in Python

Binary Search

Binary search is used for searching an element in a sorted array. Binary search works on the principle of divide and conquer technique. This searching technique looks for a particular element by comparing the middle most element of the collection.

It is useful where the large number of elements in an array.

Example             

                              5  10  15  20  25  30  35

The above array is sorted in ascending order. As we know binary search is applied on sorted lists only for fast searching.

If searching an element 25 in the seven element array. following figure shows how binary search works...

Binary searching starts with the middle element. If the element is equal to the element that we are searching then return the index value of element. If the element is less than then move to the left of the list or if the element is greater than then move to the right hand side of the list. Repeat this, until you find an element or no more element is available in the list.

Algorithm for Binary Search

Suppose we are searching an element x from a given sorted array. First we calculate the mid of array and then we basically ignore half of the elements just after one comparison.

Step 1 : Compare x with the middle element.

Step 2 : If x matches with middle element, we return the mid index value.

Step 3 : Else if x is greater than the mid element. than x can only lie in right half subarray after the mid element. so we recur the right half.

Step 4 : Else (x is smaller) recur for the lift half.

Step 5 : Repeat these steps until the element x is not found.

Implementation Program for Binary search

# Recursive Binary search

def binarysearch(arr,l,r,x):

        # check base case

        if (r>=1):

                mid=1+(r-1)//2

                # if element is present at the middle itself

                if (arr[mid]==x):

                        return mid

                # if element is smaller than mid

                elif (arr[mid]>x):

                        return binarysearch(arr,0,mid-1,x)

                # else the element can only be present in right sub array.

                else:  

                        return binarysearch(arr,mid+1,r,x)

        else:

                # element is not present in the array.

                return -1

# Driver code 

arr=[2,3,4,10,40]

x=10

# function call 

result=binarysearch(arr,0,len[arr]-1,x)

if(result!=-1):

        print("Element is present at index", + result)

else : 

        print("Element is not present in the given array")

Output

Element is present at index 3

Example

Given array is :     2  5  8  12  16  23  38  56  72  91

Let us say we want to search for 23. Now to find 23, there will be many iterations with each having steps-

Iteration 1 : Array- 2,5,8,12,16,23,38,56,72,91

Select the middle element (here 16).

Since 23 is greater than 16, so we divide the array into two halves and consider the sub-array after element 16.

Now this sub array with the elements after 16 will be taken into next iteration.

Iteration 2 : Array- 23,38,56,72,91

Select the middle element (now 56).

Since 23 is smaller than 56, so we divide the array into two halves and consider the subarray before element 56.

Now this subarray with the elements before 56 will be taken into next iteration.

Iteration 3 : Array- 23,38

Select the middle element (now 23)

Since 23 is the middle element. so the iteration will now stop.