Can you implement a function to perform a Binary Search?

Binary search is a fast search algorithm with a runtime complexity of O(log n). A binary search works by comparing an input value to the middle element of a sorted array. Depending on whether the input is less than or greater than the middle element, the algorithm "narrows down" the search to the lower or upper half of the array and repeats the process.

Here’s a simple implementation of binary search in Python:

def binary_search(arr, low, high, x):
    if high >= low: 
        mid = (high + low) // 2
        if arr[mid] == x: 
            return mid 
        elif arr[mid] > x: 
            return binary_search(arr, low, mid - 1, x) 
        else: 
            return binary_search(arr, mid + 1, high, x)
    else: 
        return -1

Here’s how this implementation works:

- The function "binary_search" takes four arguments: a sorted array "arr", the lowest index "low", the highest index "high", and the value "x" that we’re searching for.

- If ‘high‘ is greater than or equal to ‘low‘, it calculates the value of ‘mid‘ as the floor division of the sum of ‘high‘ and ‘low‘. This value indicates the index of the middle element of the current array slice.

- It then compares the middle element of the array (i.e., ‘arr[mid]‘) to ‘x‘. If they’re equal, it returns the index ‘mid‘.

- If ‘arr[mid]‘ is greater than ‘x‘, it performs a binary search on the left half of the array (i.e., from index ‘low‘ to ‘mid-1‘) and returns the result.

- If ‘arr[mid]‘ is less than ‘x‘, it performs a binary search on the right half of the array (i.e., from index ‘mid+1‘ to ‘high‘) and returns the result.

- If ‘high‘ is less than ‘low‘, it means that ‘x‘ is not present in the array, so the function returns ‘-1‘.

Here’s how you can call this function:

arr = [2, 3, 4, 10, 40] 
x = 10
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') 

This code defines a sorted array ‘arr‘ and a value ‘x‘ to search for in the array. It then calls ‘binary_search‘, passing the array, the first and last index of the array, and the value to search for. If ‘binary_search‘ returns something other than ‘-1‘, the code prints the index at which ‘x‘ is found in the array. If ‘binary_search‘ returns ‘-1‘, it prints a message indicating that ‘x‘ is not present in the array.