Binary Search

Medium · rating 1200 · Binary Search

The first line contains n. The second line has n integers in non-decreasing order. The third line contains a target. Print the 0-based index of the target, or -1 if it is absent.

Constraints: 1 ≤ n ≤ 105

Editorial

Approach

The array is sorted, so we never need to look at every element. Keep a [lo, hi] window and repeatedly probe the middle: if it equals the target we're done; if it's too small the answer must be to the right, otherwise to the left. Each step halves the search space.

Finding the leftmost index

When the middle equals the target we record it and keep searching left, so ties resolve to the first occurrence.

lo, hi, res = 0, n - 1, -1
while lo <= hi:
    m = (lo + hi) // 2
    if a[m] == t: res = m; hi = m - 1
    elif a[m] < t: lo = m + 1
    else: hi = m - 1
return res

Complexity

Time: O(log n). Space: O(1).

Related problems

Open Binary Search in Code Arena →