Python Program to implement binary search algorithm in an array

Searching is the process of finding the occurrence of an element in a group. There are many techniques used for searching, Binary search is one of them. In a search, the algorithm tests for a match in the list and returns the index where matching is found, otherwise gives a message that the element is not found in the list.

What is a Binary search algorithm? 

The binary search algorithm is also called the "half interval algorithm" or "logarithmic algorithm". It works on a sorted array, If the given array is not sorted, the elements need to be sorted first, and then searching will be implemented on it. This algorithm works on a divide and conquers method. It will first divide the list into two by taking the middle element of the list and checking whether the search element matches with the middle element. If both are equal then returns the index otherwise, the algorithm chooses any one of the sublists where the chance is more the search element to be present. This division and search of sublists will continue until the size of the sublist reduces to zero.

It works faster on large lists than the smaller ones. The binary search tree and B-tree data structures are based on binary search. The repeated division of array in half reduces the time complexity of Binary search to O(logn).

How to implement binary search in Python?

  • A function could be written to implement binary search in Python. The array and search item can be passed as input variables to the function. and,
  • Using a while loop the middle element is computed first then checks
  • If the middle element is smaller than the search item then reset the left boundary to the index next to the middle element,
  • else if the middle element is greater than the search item then reset the right boundary to the index just previous to the middle element,
  • If the above conditions are not satisfied then the middle element will be the search item, So return the middle index
  • Repeat the above process until the size of sub-arrays reduces to zero.
  • If the element doesn't exist then return -1 as the last statement in the function
  • In the main section call the function with an array, search value, and print the results according to the return value from the function

Now, let's see the working of the Binary Search Algorithm. Take an array  [ 12, 23, 26, 34, 38, 41 ] and search element 34. We have 12 at the start,41at the last, and 26 at the middle. Check if the middle one 26<34. It's true so the list to search becomes [34, 38, 41 ] i.e., the right subarray. Check if 38<34 it does not then check 38>34 it's true then now list becomes [34] and got a match, thus our search became successful.

ALGORITHM

STEP 1: Write a function binarySearch with variables array arr and search value item.

STEP 2: Initialise variables low 0 and high last index

STEP 3: Start a while loop to repeat until the condition low<=high,

STEP 4: Find the middle index of the array mid and check the middle element < item if matches then reset low=mid+1(right subarray)

STEP 5: else check if the middle element > item if matches then reset high=mid-1(left subarray)

STEP 6: else return mid means match found

STEP 6: Now end the function by return -1 means no match found

STEP 7: Initialise an array arr with values and item to be searched

STEP 8: Call the binarySearch() with values arr, item and check the return value and print the suitable result

Python Source Code

                                          def binary_search(arr, item):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
 
        mid = (high + low) // 2
 
        # If item is greater, ignore left half
        if arr[mid] < item:
            low = mid + 1
 
        # If item is smaller, ignore right half
        elif arr[mid] > item:
            high = mid - 1
 
        # means item is present at mid
        else:
            return mid
 
    # If we reach here, then the element was not present
    return -1
 
 
# Test array
arr = [ 12, 23, 26, 34, 38, 41 ]
item = 34
 
# Function call
result = binary_search(arr, item)
 
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")
                                      

OUTPUT

Element is present at index 3