Binary Search

Is a search algorithm that finds an element in a sorted array by repeatedly dividing the search area in half, and it’s time complexity is O(log n).

The implementation consists on:

1. Initializing two pointers, to mark the start and end of the search area
2. Using these pointers to calculate the middle index of the current search area
3. Comparing the element in the middle with the target element
4. Tweak the pointers based on the comparison result:
5. Repeat steps 2-4 until the target is found

How the comparison works:

• If middle element is equal to the target, return the middle index
• If the middle element is less than the target, move the start pointer to middle + 1
• If the middle element is greater than the target, move the end pointer to middle - 1

This is called “binary” search because each comparison cuts the search area in half, making it highly efficient.

Here is a Python implementation of binary search:

def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

TIP

Binary Search requires only two things: a sorted array and a comparable data type (not just integers). Array length (odd/even) doesn’t matter.