def binary_search(arr, low, high, x): # Check base case if high >= low: mid = (high + low) // 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 binary_search(arr, low, mid - 1, x) # Else the element can only be present in right subarray else: return binary_search(arr, mid + 1, high, x) else: # Element is not present in the array return -1 # Test array arr = [ 2, 3, 4, 10, 40 ] x = 10 # Function call result = binary_search(arr, 0, len(arr)-1, x) if result != -1: print("Element is present at index", str(result)) else: print("Element is not present in array")
Here are a few things to note about the above code : 1. The function is recursive and has four parameters : arr for the given array, x for the element to be searched, low and high for low and high indexes of the array. 2. The base case for recursion is when high is less than low, i.e. the subarray is exhausted without a match. In such a case, the element is not present in the array. 3. The binary search works by choosing a pivot element from the given array, comparing it with the element to be found, and then splitting the array into two halves according to whether the element to be found is less than or greater than the pivot element. 4. If the element to be found is less than the pivot element, then it can only be present in the left half of the array. Else, it can only be present in the right half of the array.