Binary Search in Python

In this Tutorial, we will go through the implementation of Binary Search Algorithm in Python and write an efficient python code about it. It is also known as half search method, logarithmic chop, or binary chop. Binary search works on logarithmic time in the worst case scenario making O(log(n)) comparisons, where n is the number of elements in the array, the O is Big O notation, and the log is the logarithm.

The binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. It is also faster than Linear search, except small linear arrays.

Performance

• Worst Case Performance: O(log(n))
• Best Case Performance: O(1)
• Average Case Performance: O(log(n))
• Worst Case Space Complexity: O(1)

Binary Search works on sorted arrays. Large data companies like Twitter, facebook often use binary search on their hash tables to find the data quickly. The binary search algorithm works as follows:

• Binary search begins by comparing the middle element of the array with the target value.
• If the target value matches the middle element, its position in the array is returned.
• If the target value is less than the middle element, the search continues in the lower half of the array.
• If the target value is greater than the middle element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration

Binary Search Pseudo Code

Let an array A with n elements with values sorted in ascending order and a target value T. The following subroutine will be used to find the index of T in A.

1. Set L to 0 and R to n-1
2. If L > R search is Unsuccessful
3. Set m to the floor of ((L+R) / 2),
4. If A[m] < T, set L = m + 1, and goto step 2.
5. If A[m] > T, set R = m – 1, and goto step 2.
6. If A[m] == T, Voila!! Search is done, return m

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

Binary Search Python Code

from math import floor

def binary_search(Array, Search_Term):
    n = len(Array)
    L = 0
    R = n-1
    
    while L <= R:
        mid = floor((L+R)/2)
        if Array[mid] < Search_Term:
            L = mid + 1
        elif Array[mid] > Search_Term:
            R = mid - 1
        else:
            return mid
    return -1


# Insert your array here
A = [1,2,3,4,7,9,12,14,18]
# term to be searched
term = 14
index = binary_search(A, term)
if index >= 0:
    print("{} is at index {}".format(A[index], index))
else:
    print("Search term not found")

Note : Array must be sorted for Binary search to work

Output

14 is at index 7

If you face any error, Please comment below. I shall be happy to help 😁

Find more variations of binary search on pyblog.in.