DSA problem
Binary Search
Given a sorted array of integers nums (in ascending order) and an integer target, return the index of target in the array. If target does not exist, return -1.
You must write an algorithm with O(log n) runtime complexity. That hard upper bound is the whole point of the problem: a linear scan, while correct, defeats the purpose of starting from a sorted input. The intent is to internalize the canonical bisection idea that underlies dozens of harder problems later on.
The classical approach maintains two pointers lo and hi that bracket the still-possible range of indices. On each iteration compute mid = lo + (hi - lo) / 2 — note the subtraction form, which prevents integer overflow when lo + hi could exceed the type's maximum value. Compare nums[mid] to target: equal means done, less means the answer is strictly to the right (lo = mid + 1), greater means strictly to the left (hi = mid - 1).
A correct binary search hinges on getting the loop invariant right and on terminating. With inclusive bounds (hi = n - 1) the loop condition is lo <= hi; each iteration always shrinks the search window by at least one because mid is excluded by the +1 / -1 updates. The result is O(log n) time and O(1) space, with no recursion stack overhead.
Examples
nums = [-1,0,3,5,9,12], target = 94nums = [-1,0,3,5,9,12], target = 2-1nums = [5], target = 50Constraints
- 1 <= nums.length <= 10^4
- -10^4 < nums[i], target < 10^4
- All integers in nums are unique.
- nums is sorted in ascending order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.