Binary Search

    DSA · Beginner

    Definition

    Binary search finds a target in a sorted array by repeatedly halving the search range.

    It reduces search from O(n) to O(log n) and appears in countless interview problems.

    Diagram

    1 3 5 7 9 11mid=7target 9 > 7search right half

    Flowchart

    Set low=0, high=n-1mid = (low+high)//2If arr[mid]==target → foundIf smaller → low=mid+1Else → high=mid-1Repeat while low<=high

    Example: Iterative binary search

    def bs(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t: return mid
        if a[mid] < t: lo = mid + 1
        else: hi = mid - 1
    return -1
print(bs([1,3,5,7,9,11], 9))

    Output: 4

    Complexity

    Time O(log n) · Space O(1)

    Key points

    • Array must be sorted
    • Watch off-by-one errors
    • Binary search on answer solves optimisation problems

    Interview questions

    Search in a rotated sorted array?

    One half is always sorted; check if target lies in it and discard the other half.

    Find first occurrence?

    On match, record index and continue searching left.

    More DSA topics

    ArraysLinked ListStackQueue