Binary Search

Efficiently find an element in a sorted array.

Binary Search is an efficient algorithm to find the position of a target element in a sorted array. Instead of checking each element one by one, it divides the search space in half with every step, making it incredibly fast for large datasets.

How the Algorithm Works

Here’s how Binary Search works:

  1. Start with two pointers: one pointing to the beginning (low) and the other to the end (high) of the array.
  2. Find the middle element (mid) of the current search space.
  3. Compare the middle element with the target:
    • If it matches the target, the search is complete.
    • If the target is smaller, narrow the search to the left half by moving the high pointer.
    • If the target is larger, narrow the search to the right half by moving the low pointer.
  4. Repeat the process until the target is found or the pointers cross.

I think the beauty of Binary Search lies in its simplicity and the way it drastically reduces the number of elements to check.

Time & Space Complexities

  • Time Complexity: O(log n), because we halve the search space at every step.
  • Space Complexity: O(1) for the iterative version, as no extra memory is used. For the recursive version, it’s O(log n) due to the call stack.

When to Use

Binary Search is your go-to algorithm when:

  • The dataset is sorted.
  • You need to quickly find an element or check for its existence.

It’s widely used in problems where searching is involved, like finding the square root, searching in rotated arrays, or even solving optimization problems.

Code Examples

Here’s an example of Binary Search:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            low = mid + 1  # Move to the right half
        else:
            high = mid - 1  # Move to the left half

    return -1  # Target not found

# Example usage
array = [1, 3, 5, 7, 9]
target = 5
result = binary_search(array, target)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")

Problems to Solve

Important Problems on Binary Search

Binary Search [NeetCode]

Resources