Implement Binary Search using Python

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most and one must continuously keep sharpening these skills. And to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are particular approaches to solve problems so that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, to keep things simple were going to start with some mediocre programs you must learn before moving on to complex algorithms. Therefore today we’re going to learn how to Implement Binary Search using Python.

 

What is Binary Search?

 

• Binary Search works only on the sorted arrays and is one of the most basic searching algorithms.

 

• The Array is firstly partitioned into two sections if the element we are searching for is less than the value at the middle index of an array. Then, we continue to partition and search for the element towards the left side. However, if the element is greater, we’ll continue to partition and search for the element towards the right side.

 

Also Read: Implement Radix Sort Using Python

 

What’s The Approach?

 

• We are going to start from the middle index of the array, if the middle index has the element we’re searching for we will simply return it.

 

• If the element is smaller than the element present at the middle index. Then, we’ll recursively search for it in the left subarray.

 

• If the element is greater than the element present at the middle index. Then, we’ll recursively search for it in the right subarray.

 

Python Program To Implement Binary Search

Input:

2, 3, 4, 10, 40

 

Output:

Element is present at index 3

 

# Python Program for binary search.


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

    # Check base case
    if r >= l:

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

        # If element is present at the middle itself
        if arr[mid] == x:
            return mid
        
        # If element is smaller than mid, then it
        # can only be present in left subarray
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)

        # Else the element can only be present
        # in right subarray
        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 % d" % result)
else:
    print ("Element is not present in array")