Binary Search

Tags

Binary Search

Category

Searching

Difficulty

Easy

Problem Statement

Given a sorted array of integers and a target value, implement binary search to find the index of the target in the array. If the target is not present, return -1.

Intuition

In a sorted array, we can eliminate half the remaining elements with each comparison. By comparing the target to the middle element, we determine whether to search the left or right half. This halving process gives logarithmic time complexity.

Approach

  1. Initialize two pointers: left = 0 and right = length - 1.
  2. While left <= right:
    • Compute mid = left + (right - left) / 2 (avoids overflow).
    • If array[mid] == target, return mid.
    • If array[mid] < target, set left = mid + 1.
    • If array[mid] > target, set right = mid - 1.
  3. If the loop exits, the target is not in the array — return -1.

Pseudocode

function binarySearch(array, target):
    left = 0
    right = length(array) - 1
    while left <= right:
        mid = left + (right - left) / 2
        if array[mid] == target:
            return mid
        else if array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Time & Space Complexity

  • Time: O(log n) — The search space is halved at every step.
  • Space: O(1) for the iterative version. O(log n) for a recursive version due to the call stack.

Key Insights

  • The array must be sorted for binary search to work.
  • Using left + (right - left) / 2 instead of (left + right) / 2 prevents integer overflow.
  • Binary search can be adapted for many problems: finding insertion points, first/last occurrence, or searching on answer spaces.
  • Off-by-one errors are the most common source of bugs — carefully define whether bounds are inclusive or exclusive and maintain that invariant.

System Design Application

Binary search on a sorted array is the ring lookup mechanism in Consistent-Hashing. When a key is hashed to a position on the consistent hash ring, the system performs a binary search (or equivalent sorted-array scan) on the sorted list of virtual node positions to find the first node whose hash is >= the key hash. This lookup runs in O(log V) where V is the number of virtual nodes on the ring.

Edge Cases

  • Empty array — return -1 immediately.
  • Single-element array — one comparison determines the result.
  • Target is smaller than all elements — right drops below left on the first iteration.
  • Target is larger than all elements — left exceeds right after scanning rightward.
  • Target appears multiple times — standard binary search returns one occurrence (not necessarily the first or last).

Linked mentions