Find a value in a sorted array
Given an array nums of distinct integers sorted in increasing order, and an integer
target, return the index of target in nums, or −1 if it is
not there. The search must take O(log n) comparisons.
Examples
| Input | Output | Why |
|---|---|---|
nums = [-4, 0, 3, 8, 12, 19], target = 8 | 3 | |
nums = [-4, 0, 3, 8, 12, 19], target = 5 | -1 | 5 would sit between 3 and 8. |
nums = [7], target = 7 | 0 |
Constraints
- 1 ≤ n ≤ 10⁵
- −10⁹ ≤ nums[i], target ≤ 10⁹
- nums is strictly increasing
Hints
Hint 1
Compare target with the middle element. Whichever way the comparison goes, one half of the array cannot contain target.
Hint 2
Keep two indices, lo and hi, with the rule "if target is anywhere, it is in nums[lo..hi]". Every update must keep that rule true.
Hint 3
If nums[mid] < target, then lo = mid + 1; if nums[mid] > target, then hi = mid − 1. Stop when lo > hi: the range is empty.
Where people lose marks
- Writing
while (lo < hi)withhi = mid − 1: the last remaining element is never checked. - Setting
lo = midinstead ofmid + 1: when hi = lo + 1, mid equals lo and the loop never ends. - Computing
(lo + hi) / 2in a language with fixed-width integers.
Dry run on [-4,0,3,8,12,19,23,31,40],23
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 3lo0hi8
Looking for 23. If it is anywhere, it is in [lo, hi] = [0, 8]: the whole array.
-
Step 2 / 3lo0mid4hi8a[mid]12
a[4] = 12 < 23. Everything from index 0 to 4 is at most 12, so none of it can be 23: lo = 5.
-
Step 3 / 3lo5mid6hi8
a[6] = 23, the target. Return 6.
How to think about it
Keep the range [lo, hi] of indices that could still hold target, starting with the
whole array. Look at the middle element:
- If it equals
target, return its index. - If it is smaller, every element at or before
midis smaller too, because the array is sorted. Discard them:lo = mid + 1. - If it is larger, discard
midand everything after it:hi = mid − 1.
Each step at least halves the range, so after about log₂ n steps it is empty or the value has been found. The
loop condition lo ≤ hi follows from the meaning of the range: a closed range with
lo = hi still holds one element that must be checked.
Compute the middle as lo + (hi − lo) / 2. With 32-bit integers,
(lo + hi) / 2 overflows once the indices pass about 1.07 × 10⁹; the bug sat unnoticed in Java's
standard library for nine years.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # if target is anywhere, it is in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # nums[lo..mid] are all too small
else:
hi = mid - 1 # nums[mid..hi] are all too large
return -1#include <vector>
int solve(const std::vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1; // if target is anywhere, it is in nums[lo..hi]
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // no overflow
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1; // if target is anywhere, it is in nums[lo..hi]
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // no overflow
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
}function search(nums, target) {
let lo = 0, hi = nums.length - 1; // if target is anywhere, it is in nums[lo..hi]
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] === target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}fn solve(nums: &[i64], target: i64) -> i64 {
// half-open [lo, hi) keeps the indices unsigned: hi = mid never goes below zero
let (mut lo, mut hi) = (0usize, nums.len());
while lo < hi {
let mid = lo + (hi - lo) / 2;
if nums[mid] == target {
return mid as i64;
}
if nums[mid] < target { lo = mid + 1 } else { hi = mid }
}
-1
}import Data.Array
solve :: [Int] -> Int -> Int
solve nums target = go 0 (n - 1)
where
n = length nums
a = listArray (0, n - 1) nums
-- if target is anywhere, it is in a[lo..hi]
go lo hi
| lo > hi = -1
| a ! mid == target = mid
| a ! mid < target = go (mid + 1) hi
| otherwise = go lo (mid - 1)
where mid = lo + (hi - lo) `div` 2Variants to try
- The array may contain duplicates and you want the first occurrence: the lower-bound search in the next module.
- The value is absent and you want where it would go: return lo when the loop ends.
- The array has been rotated: decide which half is sorted before discarding one.
Next problems
Integer square root without a library
Search the candidates 0 to n for the last x with x² ≤ n, and keep the square from overflowing.
Open the problem → Easy10 minThe top of a mountain array
Nothing is sorted, but "is the next element smaller?" is false up the slope and true down it. Find the first true.
Open the problem → Easy10 minWhere a value belongs in a sorted array
Return the first position whose element is at least the target: the lower bound, which answers both "is it here" and "where would it go".
Open the problem →Write a solution and run it against the real test table.
Keep going
Integer square root without a library
Search the candidates 0 to n for the last x with x² ≤ n, and keep the square from overflowing.
Open the problem → Easy10 minThe top of a mountain array
Nothing is sorted, but "is the next element smaller?" is false up the slope and true down it. Find the first true.
Open the problem → Easy10 minWhere a value belongs in a sorted array
Return the first position whose element is at least the target: the lower bound, which answers both "is it here" and "where would it go".
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.