Binary Search Boundaries: Find the First Match Safely

By Hourly DSA · September 20, 2026 · 4 min read

Reliable binary search starts with a precise question and a consistent interval convention. “Find any matching value” and “find the first matching value” are different tasks. Their boundary updates need to preserve different possibilities.

Let's solve one useful version: find the first position whose value is at least a target in an ascending sorted array. This is often called a lower bound.

Define what the answer means

For [1, 3, 3, 7] and target 3, the answer is index 1. For target 4, the answer is index 3, where 7 appears. For target 8, the answer is 4, the position just past the array.

Returning n when no element qualifies gives the operation a consistent meaning: where could you insert the target without breaking sorted order?

That also handles an empty array. Its only insertion position is zero.

Use a half-open search interval

We'll maintain [left, right): left is included, right is excluded. Initially, left is 0 and right is n.

The invariant, or fact we keep true, is:

Every position before left has a value below the target.
Every position at or after right has a value at least the target.
Positions from left through right minus one still need examination.

At the start, both excluded regions are empty, so those statements hold automatically.

The complete search in a few lines

left = 0
right = length(values)
while left < right:
    mid = left + floor((right - left) / 2)
    if values[mid] < target:
        left = mid + 1
    else:
        right = mid
return left

When values[mid] is below the target, mid cannot be the answer. Sorted order also rules out everything before it, so left moves past mid.

Otherwise, mid qualifies, but an earlier position might qualify too. Setting right to mid keeps that boundary as a possible result while narrowing the unexplored positions to its left.

Don't use right = mid - 1 in this version. That update belongs to a different interval convention and can skip the correct boundary.

Trace a duplicate value

Search for the first value at least 3 in [1, 3, 3, 7]:

right	mid	Decision
4	2	Value 3 qualifies; set right to 2
2	1	Value 3 qualifies; set right to 1
1	0	Value 1 is too small; set left to 1

Now left equals right, so return 1.

Finding a matching value at index 2 didn't end the search. It told us that the first qualifying value could be at 2 or earlier. That's the distinction that makes duplicates behave correctly.

Why this loop makes progress

When left < right, mid is at least left and strictly below right. Either update reduces the unexplored interval:

left = mid + 1 increases left.
right = mid decreases right.

If you used left = mid, a one-element interval could remain unchanged forever. For example, left 0 and right 1 give mid 0. Assigning left to 0 accomplishes nothing.

Progress is part of correctness. A search that preserves candidates but never finishes still fails.

Turning the boundary into an exact search

A lower bound can point to a larger value or to n. To check whether the target exists, verify both:

The returned index is less than n.
The value at that index equals the target.

Check the first condition before accessing the array. An answer of n is a valid insertion position but not a valid element index.

Complexity and quick edge cases

Each iteration roughly halves the unexplored range. With constant-time array access, the search takes O(log n) time and O(1) extra space.

Before trusting your implementation, trace an empty array, one element, repeated targets, a target below every value, and a target above every value. These cases exercise the interval rules directly.

For daily practice, ask yourself why each update is safe before looking at code. Hourly DSA gives you short reasoning questions that fit that habit. If the logarithmic bound still feels abstract, see Big O notation through small examples.