7  Binary Search

Rank 5 · Pattern: halve an ordered search interval · Target: \(O(\log n)\) time, \(O(1)\) space

7.1 Problem definition

Given an integer array nums sorted in ascending order and an integer target, return an index at which target occurs, or the language’s conventional absence result.

7.2 Clarifying questions

  1. Is the array guaranteed to be sorted, and in which direction?
  2. Can duplicate values occur? If so, which matching index should I return?
  3. Can the array be empty or null?

7.3 Sample answers

  1. Yes. The array is sorted in ascending order.
  2. Duplicates may occur, and any matching index is acceptable.
  3. The array is non-null. An empty array is allowed and should produce -1 in Java/Python or None in Rust.

7.4 Approach and invariant

Maintain a candidate interval and state its boundary convention before coding.

Use the inclusive interval [low, high]. It is empty when low > high, so the loop uses low <= high and discards the midpoint with mid + 1 or mid - 1.

int mid = low + (high - low) / 2;

Use the same inclusive interval [low, high]. Integer floor division computes middle = low + (high - low) // 2.

Use the half-open interval [low, high), with high = nums.len(). It is empty when low == high; discarding the left half uses low = middle + 1, while discarding the right half uses high = middle. This avoids subtracting from an unsigned index.

Invariant: if the target exists and has not been returned, at least one matching index lies in the current candidate interval.

For target 7 in [-4,0,3,7,12]:

low high mid value next interval
0 4 2 3 [3,4]
3 4 3 7 return 3 
[-4, 0, 3, 7, 12]
  L     M       H      3 < 7: discard through M
           L M  H      found

7.5 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class BinarySearchSolution {
    static int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int value = nums[mid];

            if (value == target) {
                return mid;
            }
            if (value < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    @Test public void emptyArrayHasNoMatch() {
        assertEquals(-1, search(new int[0], 2));
    }

    @Test public void findsOnlyValue() {
        assertEquals(0, search(new int[] {2}, 2));
    }

    @Test public void rejectsAbsentValueFromSingleton() {
        assertEquals(-1, search(new int[] {2}, 1));
    }

    @Test public void findsMiddleValue() {
        assertEquals(3, search(new int[] {-4, 0, 3, 7, 12}, 7));
    }

    @Test public void findsFirstValue() {
        assertEquals(0, search(new int[] {1, 3, 5}, 1));
    }

    @Test public void findsLastValue() {
        assertEquals(2, search(new int[] {1, 3, 5}, 5));
    }

    @Test public void returnsMinusOneForValueBetweenElements() {
        assertEquals(-1, search(new int[] {1, 3, 5}, 4));
    }

    @Test public void returnsMinusOneOutsideArrayRange() {
        assertEquals(-1, search(new int[] {1, 3, 5}, 0));
        assertEquals(-1, search(new int[] {1, 3, 5}, 6));
    }

    @Test public void mayReturnAnyDuplicateIndex() {
        int index = search(new int[] {1, 2, 2, 2}, 2);
        assertTrue(index >= 1 && index <= 3);
    }

    public static void main(String[] args) {
        JUnitCore.main("BinarySearchSolution");
    }
}
import unittest


def search(nums, target):
    low = 0
    high = len(nums) - 1

    while low <= high:
        middle = low + (high - low) // 2
        value = nums[middle]

        if value == target:
            return middle
        if value < target:
            low = middle + 1
        else:
            high = middle - 1

    return -1


class BinarySearchTests(unittest.TestCase):
    def test_empty_array(self):
        self.assertEqual(-1, search([], 2))

    def test_finds_only_value(self):
        self.assertEqual(0, search([2], 2))

    def test_rejects_absent_singleton_value(self):
        self.assertEqual(-1, search([2], 1))

    def test_finds_middle_value(self):
        self.assertEqual(3, search([-4, 0, 3, 7, 12], 7))

    def test_finds_boundaries(self):
        self.assertEqual(0, search([1, 3, 5], 1))
        self.assertEqual(2, search([1, 3, 5], 5))

    def test_rejects_absent_value(self):
        self.assertEqual(-1, search([1, 3, 5], 4))

    def test_may_return_any_duplicate_index(self):
        self.assertIn(search([1, 2, 2, 2], 2), range(1, 4))


if __name__ == "__main__":
    unittest.main()
pub fn search(nums: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = nums.len();

    while low < high {
        let middle = low + (high - low) / 2;

        if nums[middle] == target {
            return Some(middle);
        }
        if nums[middle] < target {
            low = middle + 1;
        } else {
            high = middle;
        }
    }

    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_array() {
        assert_eq!(None, search(&[], 2));
    }

    #[test]
    fn finds_only_value() {
        assert_eq!(Some(0), search(&[2], 2));
    }

    #[test]
    fn rejects_absent_singleton_value() {
        assert_eq!(None, search(&[2], 1));
    }

    #[test]
    fn finds_middle_value() {
        assert_eq!(Some(3), search(&[-4, 0, 3, 7, 12], 7));
    }

    #[test]
    fn finds_boundaries() {
        assert_eq!(Some(0), search(&[1, 3, 5], 1));
        assert_eq!(Some(2), search(&[1, 3, 5], 5));
    }

    #[test]
    fn rejects_absent_value() {
        assert_eq!(None, search(&[1, 3, 5], 4));
    }

    #[test]
    fn may_return_any_duplicate_index() {
        assert!(matches!(search(&[1, 2, 2, 2], 2), Some(1..=3)));
    }
}

7.6 High-value tests

Case Input / target Expected
empty [] / 4 absent
one, present [4] / 4 0
one, absent [4] / 3 absent
first [1,3,5] / 1 0
last [1,3,5] / 5 2
between values [1,3,5] / 4 absent
duplicate contract [1,2,2,2] / 2 any of 1–3

7.7 Complexity and correctness

Each comparison removes at least half the remaining candidates, so time is \(O(\log n)\) and iterative space is \(O(1)\).

When the midpoint is smaller than target, sorted order proves every earlier value is also too small; the symmetric argument holds when it is larger. Thus each update preserves the invariant. If the interval becomes empty, no candidate remains.

7.8 If the interviewer pushes

  • To find the first occurrence, save a match and continue left, or use a lower-bound search.
  • To find an insertion position, return low after the loop.
  • For a monotonic predicate rather than an array, binary-search the first true value with carefully chosen bounds.
  • Recursive binary search has the same time but \(O(\log n)\) call-stack space and more boundary plumbing.

7.9 TDD interview script

Confirm the array is non-null and ascending, empty input is allowed, the language’s absence value is defined, and any duplicate match is acceptable. Then write this test list:

  1. Empty array
  2. Singleton present
  3. Singleton absent
  4. Middle value
  5. First value
  6. Last value
  7. Missing interior value
  8. Values outside the array range
  9. Duplicates

Use one red–green–refactor cycle per focused behavior. Run the expected failure, make the smallest boundary update that passes, then rerun the complete example. Avoid testing private pointer movements; the first, last, singleton, and absent cases expose off-by-one errors through public results.

From book/src, run:

./java/run.sh BinarySearchSolution
./python/run.sh binary_search_solution
./rust/run.sh binary_search_solution

State the interval convention before coding. Java and Python use an inclusive interval here; Rust uses a half-open interval to keep unsigned-index arithmetic simple. Either works, but mixing their update rules creates off-by-one errors.

7.9.1 Pseudocode

low = 0
high = nums.length - 1

while low <= high:
    mid = low + (high - low) / 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

return -1

The Java pseudocode uses the same inclusive interval; replace nums.length with len(nums).

low = 0
high = nums.length

while low < high:
    middle = low + (high - low) / 2
    if nums[middle] == target:
        return Some(middle)
    if nums[middle] < target:
        low = middle + 1
    else:
        high = middle

return None

The invariant is: if the target exists and has not been returned, at least one matching index remains inside the selected candidate interval.

7.9.2 TDD sequence

Step Test code added Production code added or changed
1. Empty interval emptyArrayHasNoMatch Initialize high to length - 1, use low <= high, and return -1 when the interval is empty.
2. Singleton hit findsOnlyValue Compute the midpoint and return it on equality.
3. Singleton miss rejectsAbsentValueFromSingleton Add the less-than and greater-than branches with mid + 1 and mid - 1, guaranteeing progress.
4. Repeated halving findsMiddleValue Loop while candidates remain and retain the appropriate half after each comparison.
5. Left boundary findsFirstValue Verify that an inclusive interval can retain index zero.
6. Right boundary findsLastValue Verify that the final array index is retained and examined.
7. Interior miss returnsMinusOneForValueBetweenElements Confirm that crossing the bounds terminates rather than looping between adjacent values.
8. Exterior misses returnsMinusOneOutsideArrayRange Exercise repeated movement in each direction until no candidates remain.
9. Duplicate contract mayReturnAnyDuplicateIndex Assert only that the returned index is one of the valid duplicate positions; do not over-specify first or last.

This progression treats interval boundaries as the primary risk. The examples triangulate the inclusive-loop template and the duplicate test preserves freedom that the contract explicitly allows.