Binary Search Algorithm in Python

Binary search is a search algorithm that finds the position of a target value within a sorted array. The process starts by comparing the target value to the middle element of the array. If the target value matches the middle element, the search ends. If the target value is less than the middle element, the search continues on the lower half; if it is greater, the search continues on the upper half. The process repeats, reducing the search space by half each time. If the array becomes empty, it means the target is not in the array.

Example: Recursive Binary Search

The following code demonstrates how to implement binary search using recursion.

# Return the index of 'x' in 'arr', or -1 if it doesn't exist
def binarySearch(arr, l, r, x):
  
    # Basic check
    if r >= l:
  
        mid = int(l + (r - l) / 2)
  
        # If the element is present at the middle
        if arr[mid] == x:
            return mid
  
        # If the element is smaller than mid, search the left subarray
        elif arr[mid] > x:
            return binarySearch(arr, l, mid - 1, x)
  
        # If the element is larger than mid, search the right subarray
        else:
            return binarySearch(arr, mid + 1, r, x)
  
    else:
        # Element not found
        return -1
  
# Test array
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 the array")

Output:

Element is present at index 3

This code first checks if the middle element of the array matches the target value. If it doesn’t, it continues searching in either the left or right half of the array depending on whether the middle element is greater than or less than the target value.