Binary Search

Binary search is an efficient algorithm for finding an element in a sorted list. It works by repeatedly dividing the list in half, until the element is found or it is clear that the element is not in the list.

Here’s the basic outline of the algorithm:

1) Set the lower bound low to the first index of the list and the upper bound high to the last index.
2) While low is less than or equal to high, repeat the following:
Set the middle index mid to the floor of the average of low and high.
If the element at index mid is the element being searched for, return mid.
If the element at index mid is greater than the element being searched for, set high to mid – 1.
If the element at index mid is less than the element being searched for, set low to mid + 1.
3) If the element is not found, return null or some other sentinel value.

function binary_search(array, element):
    low = 0
    high = length of array - 1
    while low <= high:
        mid = floor((low + high) / 2)
        if array[mid] == element:
            return mid
        else if array[mid] > element:
            high = mid - 1
        else:
            low = mid + 1
    return null