Understanding the Problem

We're given a sorted array of unique integers and need to find the index of a specific target value. If the target isn't in the array, we return -1.

Sorted order means we don't have to look at every element. Comparing any element to the target tells us whether the target lies to its left or to its right, so a single comparison eliminates an entire region of the array. Binary search applies this comparison at the midpoint, discarding half of the remaining range each time.

Key Constraints:

1 <= nums.length <= 10^4 → With n up to 10,000, even an O(n) linear scan would be fast enough in practice. But the problem requires O(log n), which calls for binary search.
-10^4 < nums[i], target < 10^4 → Small value range. Since n ≤ 10^4, (left + right) / 2 would not overflow here. The code below uses left + (right - left) / 2 anyway as a defensive habit. It generalizes to problems with larger bounds and costs nothing.
All integers in nums are unique → There is at most one match, so the first index where nums[mid] == target is the answer. With duplicates we would need extra logic to find the leftmost occurrence.
nums is sorted in ascending order → Sorted order is what binary search depends on. Without it, comparing the middle element tells us nothing about which half holds the target.

Approach 1: Linear Scan

A linear scan checks each element in turn, which takes O(n) time and O(1) space. It ignores the sorted order entirely and does not meet the required O(log n), so we skip the full implementation and move straight to binary search.

Approach 2: Binary Search

Intuition

Since the array is sorted, we can do better than checking one element at a time. Pick the middle element. If it equals the target, we're done. If the target is smaller, it must be in the left half. If the target is larger, it must be in the right half. Either way, we've eliminated half the array with a single comparison.

This is the same approach as guessing a number between 1 and 100 by asking "higher or lower?". Start at 50, then 25 or 75, and keep halving the range.

Correctness

Binary search maintains an invariant: after every iteration, the target (if it exists) is still within the range [left, right]. When nums[mid] < target, the target can't be at mid or anywhere to its left (the array is sorted), so moving left past mid never discards it. The same logic applies in reverse when nums[mid] > target.

The loop terminates when left > right, which means the search range is empty. At that point, every possible position for the target has been eliminated, so it doesn't exist in the array.

Algorithm

Set left = 0 and right = nums.length - 1.
While left <= right:

Compute mid = left + (right - left) / 2.
If nums[mid] == target, return mid.
If nums[mid] < target, set left = mid + 1 (target is in the right half).
If nums[mid] > target, set right = mid - 1 (target is in the left half).

If the loop ends without finding the target, return -1.

Example Walkthrough

1Initialize: left=0, right=5, search range is entire array

-1

left

right

search range

1/5

Code

Complexity Analysis

Time Complexity: O(log n). Each comparison halves the search space. Starting from n elements, we need at most log2(n) + 1 comparisons. For n = 10,000, this means at most 14 comparisons instead of 10,000.
Space Complexity: O(1). We only use three variables: left, right, and mid. No extra data structures.

When to Generalize: Predicate-Based Binary Search

The basic find-the-element template extends to a much broader class of problems through the predicate framing:

Given a monotonic predicate pred(x) that returns false-false-false-...-true-true-true over the search range, find the smallest x where pred(x) is true.

This single framing covers:

Finding the first occurrence of a target in a sorted array with duplicates (predicate: nums[x] >= target).
Finding the insertion point for a target in a sorted array (same predicate).
Binary search on answer space, such as Koko Eating Bananas or Capacity to Ship Packages Within D Days, where the search space is the set of possible answers rather than array indices.
Square root and other problems with real-valued answers, where the bounds are floating-point and the loop terminates when the range shrinks below a chosen epsilon.

The search in this chapter is a special case of the same idea: with the predicate nums[x] >= target, find the smallest index where it holds, then check whether the element there equals the target. Once a problem can be phrased as a monotonic predicate over an ordered range, the same halving loop applies, whether the range is array indices or candidate answers.