DSA SheetEasy
EditorialPractice

BINARY SEARCH › INTRODUCTORY PROBLEMS

Binary Search

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A sorted array with an inclusive search interval shrinking around its middleDraw a row of indexed cells whose values increase from left to right. Bracket the current inclusive interval between left and right, and highlight its middle cell. Show an arrow from a middle value smaller than the target to a new left boundary just after the middle, while the right boundary stays fixed; the discarded left half is crossed out. The picture makes clear that one comparison removes half of the remaining candidates.71218232934414856630123456789inclusive interval [0..9]mid = 4, compare A[mid] = 2929 < target → left: 0 → 5keep [5..9]29 > target → right: 9 → 3keep [0..3]

Approachmaintain one inclusive interval

  1. 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.
  2. Repeat while left <= right, because equality means one candidate remains and must still be tested; stopping at left < right would skip that final index.
  3. Compute mid as left + (right - left) / 2, because it finds the midpoint without forming the potentially overflowing sum left + right.
  4. 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.
  5. 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.
  6. Otherwise set right to mid - 1, because mid and every index after it are too large and must leave the candidate interval.
  7. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraOnly 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.

Common mistakesthe interval convention must stay consistent