Binary Search Algorithm

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. The idea is to determine, in logarithmic time, whether the item you are searching for is in the lower or upper half of the interval. If it is in the lower half, you repeat the process on that half; if it is in the upper half, you repeat the process on that half. This process continues until the item is found or the search interval is empty.

Here is an example of a binary search algorithm implemented in Python.

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3)) # Output: 1
print(binary_search(my_list, -1)) # Output: None

In this example, we define a function called binary_search() that takes in two parameters: an array and a target element. The function uses a while loop to repeatedly divide the array in half until the target element is found or the array is exhausted. The loop starts by setting two pointers, left and right, to the first and last elements of the array, respectively. The pointer mid is set to the middle of the array by taking the average of left and right. If the element at the mid index is equal to the target element, the function returns the index of the target element. If the element at the mid index is less than the target element, the left pointer is set to one position to the right of mid. If the element at the mid index is greater than the target element, the right pointer is set to one position to the left of mid. The loop continues until the left pointer is greater than the right pointer, at which point the function returns -1 to indicate that the target element was not found in the array. It’s important to note that the array should be sorted to be able to use binary search. In the example above, the array is sorted in ascending order. Binary search has a time complexity of O(log n) which is faster than linear search (O(n)), which makes it suitable for large datasets.

JavaScript and C++ example on this post