Binary Search — Editorial

Opening the reading…

Intuitionwhy one comparison can remove half the candidates

The array is sorted, so the middle value tells you which half could still contain the target. If nums[mid] is smaller than target, every index at or left of mid is also too small. If nums[mid] is larger, every index at or right of mid is too large. Only the opposite half remains worth searching.

Keep an inclusive interval from left to right containing every index that has not been ruled out. Each comparison either returns mid immediately or moves one boundary past mid, so the interval strictly shrinks. When left passes right, no candidate index remains and returning -1 is justified rather than guessed.

Approachmaintain one inclusive interval

Set left to 0 and right to nums.size() - 1, because the first search interval must include every valid index and an inclusive interval needs the last index as its right boundary.

Repeat while left <= right, because equality means one candidate remains and must still be tested; stopping at left < right would skip that final index.

Compute mid as left + (right - left) / 2, because it finds the midpoint without forming the potentially overflowing sum left + right.

If nums[mid] equals target, return mid immediately, because the required answer is the index of any matching value and distinctness guarantees there is only one.

If nums[mid] is smaller than target, set left to mid + 1, because mid and every index before it are too small and keeping mid would repeat the same comparison.

Otherwise set right to mid - 1, because mid and every index after it are too large and must leave the candidate interval.

Return -1 after the loop, because left > right proves that every array index has been ruled out without finding target.

Complexitythe interval halves at every iteration

MEASURE	BOUND	WHY
Time	O(log n)	The interval has at most n indices initially and each iteration removes at least half of its current candidates. After O(log n) halvings, it is empty or contains the target; each iteration performs only constant-time arithmetic and comparisons.
Space	O(1) extra	Only left, right, mid, and a few scalar values are stored, so working memory does not grow with n. The returned index is a single value rather than a stored output structure, and the worst input shape changes neither the constant space bound nor the logarithmic search process.

Here n is the number of elements in nums; the base of the logarithm is irrelevant to Big-O notation.

Annotated solutionC++ · iterative inclusive-interval search

CPPIteratively narrow an inclusive interval until the target is found or no index remains.

#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

The two boundary updates are deliberately exclusive: after checking mid, that index is no longer a candidate. Moving to mid + 1 or mid - 1 both shrinks the interval and guarantees progress. The safe midpoint formula is also worth retaining as a habit even when this problem's values are small, because index arithmetic can overflow in larger arrays.