Binary search finds a target by repeatedly discarding a portion of a sorted search space. Its central requirement is a rule that makes one portion impossible. The recording contrasts searching methods and then follows the midpoint decisions. A correct implementation needs both that exclusion argument and boundary updates that always make progress.
Choose one interval convention
With an inclusive interval, low and high both identify candidates. The interval is empty when low passes high. A midpoint match can return immediately for an ordinary exact-match contract. Otherwise, move a boundary beyond the midpoint because that position has already been ruled out.
For [2, 5, 8, 11, 14] and target 11, the first midpoint contains 8. Sorted order proves that 8 and every earlier value are too small. The remaining candidates are 11 and 14. That proof depends on ordering; applying the same updates to an unsorted array would discard possible answers.
Decide what duplicates mean
Finding any matching position, the first matching position, and the insertion boundary are different tasks. Returning at the first equality does not establish that a match is the first one. Boundary-search variants often keep a match as a candidate and continue on one side. State the requested result before translating the general idea into code.
Check an empty array, one item, two items, a missing target, and a target at either end. Two-item intervals are particularly useful for catching a boundary that fails to move. In a fixed-width language, calculating the midpoint from the distance between boundaries can avoid overflowing their sum.
Count comparisons and representation costs
Under bounded-cost comparisons and direct indexed access, each step halves the candidate count, giving logarithmic time. The iterative version needs constant auxiliary storage. A linked list does not offer the same direct midpoint access; reaching a midpoint can require traversal, changing the cost model.
Continue with First Bad Version, where the target is a true/false transition, and Shifted Search, where you first determine which half is sorted. For either follow-up, explain the exact property that makes a discarded interval impossible instead of memorizing a set of boundary assignments.
Search for the first occurrence
For the sorted input [1, 3, 3, 3, 8] and target 3, the example returns index 1. It computes a lower bound using a half-open interval [low, high). Values before low are known to be too small. Values at or after high are outside the remaining candidates for the first position that could hold the target.
When the middle value is smaller than the target, low becomes middle + 1. Otherwise high becomes middle, keeping a matching middle value available while looking farther left. On termination low equals high. One final equality check distinguishes an actual match from an insertion position.
Test interval edges and duplicate values
An empty input begins with both bounds at zero and returns −1 after the final guard. A target above every element produces an insertion position equal to the length, so indexing before checking that bound would be an error. Targets below the first element and repeated targets exercise the opposite boundary.
The function assumes the values are already sorted in ascending order. Sorting inside a wrapper changes both its cost and the meaning of the returned index. The search itself uses O(log n) comparisons and O(1) additional storage for random-access input. If you use a linked structure instead, reaching the middle is no longer a constant-time indexing operation. Keep that representation cost in the explanation.
Rust example and implementation choices
The function borrows &[i32], so the search neither owns nor mutates the values. Its internal indices are usize, while the public result is a signed integer so −1 can denote absence. The small-example contract avoids narrowing an enormous index on return. Equality narrows the upper boundary, preserving the first occurrence among duplicates rather than returning whichever middle match appears first.
Worked example
fn binary_search(values: &[i32], target: i32) -> i32 {
let (mut low, mut high) = (0, values.len());
while low < high {
let middle = low + (high - low) / 2;
if values[middle] < target { low = middle + 1; } else { high = middle; }
}
if low < values.len() && values[low] == target { low as i32 } else { -1 }
}
Continue in Rust
Open Searching and Binary Search for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Rust example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Rust interview preparation guide connects these language choices with further practice and the cross-language operation reference.