Halving a sorted array
Think of looking up a word in a paper dictionary. You open it near the middle, see that “mango” comes after the page you’re on, and from that moment you ignore the whole first half. Then you split the second half, and so on. Each look throws away half of what’s left.
It only works because the dictionary is sorted. With a sorted array:
- look at the middle element,
- if it’s the target, you’re done,
- if it’s smaller than the target, the target can only be to the right: continue there,
- if it’s bigger, continue to the left,
- if nothing is left, the target isn’t there.
Halving each step means O(log n) time: about 20 steps for a million elements.
Binary search finds the boundary of a monotonic predicate over an ordered domain in O(log n) evaluations: the first index where nums[i] >= target, the first version that’s bad, the smallest speed that’s fast enough. Searching sorted arrays is just the most common predicate.
The correctness details are all in the invariant: which interval (closed [low, high] or half-open [low, high)) still contains the answer, and making sure every iteration shrinks it, which rules out infinite loops. Senior-level questions add binary search on the answer (over a value range instead of an array), overflow in the midpoint, library APIs with surprising return values, and rotated or partially sorted inputs. All in the Detailed version.
func binarySearch(_ nums: [Int], _ target: Int) -> Int? {
var low = 0
var high = nums.count - 1 // the answer is in [low, high]
while low <= high {
let mid = low + (high - low) / 2
if nums[mid] == target { return mid }
if nums[mid] < target {
low = mid + 1 // target is to the right of mid
} else {
high = mid - 1 // target is to the left of mid
}
}
return nil // nothing left: not found
}fun binarySearch(nums: IntArray, target: Int): Int {
var low = 0
var high = nums.size - 1 // the answer is in [low, high]
while (low <= high) {
val mid = low + (high - low) / 2
when {
nums[mid] == target -> return mid
nums[mid] < target -> low = mid + 1 // target is to the right of mid
else -> high = mid - 1 // target is to the left of mid
}
}
return -1 // nothing left: not found
}static int binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1; // the answer is in [low, high]
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) {
low = mid + 1; // target is to the right of mid
} else {
high = mid - 1; // target is to the left of mid
}
}
return -1; // nothing left: not found
}function binarySearch(nums: number[], target: number): number {
let low = 0;
let high = nums.length - 1; // the answer is in [low, high]
while (low <= high) {
const mid = low + Math.floor((high - low) / 2); // / alone gives fractions
if (nums[mid] === target) return mid;
if (nums[mid] < target) {
low = mid + 1; // target is to the right of mid
} else {
high = mid - 1; // target is to the left of mid
}
}
return -1; // nothing left: not found
}Three details make this version correct:
low <= high: the search range includes both ends, so a range of one element (low == high) still gets checked.mid + 1andmid - 1:midhas already been checked, so it’s excluded. Every step makes the range smaller, so the loop can’t run forever.low + (high - low) / 2instead of(low + high) / 2: the same value, but it can’t overflow when the numbers are huge (more on that in the senior section). In TypeScript,/doesn’t round, so the division goes insideMath.floor.
Search Insert Position
Given a sorted array of distinct integers and a target, return the index of the target if it’s there. If not, return the index where it would be inserted to keep the array sorted. It must run in O(log n).
nums = [1, 3, 5, 6], target = 5 → 2
nums = [1, 3, 5, 6], target = 2 → 1
nums = [1, 3, 5, 6], target = 7 → 4›
Run the classic binary search. When the target isn’t found, the loop ends with low > high. Where is low pointing at that moment?
›
Everything left of low is smaller than the target, and everything from high + 1 on is bigger. When the loop ends, low == high + 1: exactly the insertion point.
SolutionTry it yourself firstTime O(log n)Space O(1)
Return low instead of “not found”. The loop keeps an invariant: every element before low is smaller than the target, and every element after high is bigger. When the range is empty, low is the first position whose element is bigger, which is where the target belongs.
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
var low = 0
var high = nums.count - 1
while low <= high {
let mid = low + (high - low) / 2
if nums[mid] == target { return mid }
if nums[mid] < target { low = mid + 1 } else { high = mid - 1 }
}
return low
}fun searchInsert(nums: IntArray, target: Int): Int {
var low = 0
var high = nums.size - 1
while (low <= high) {
val mid = low + (high - low) / 2
when {
nums[mid] == target -> return mid
nums[mid] < target -> low = mid + 1
else -> high = mid - 1
}
}
return low
}int searchInsert(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) low = mid + 1; else high = mid - 1;
}
return low;
}function searchInsert(nums: number[], target: number): number {
let low = 0;
let high = nums.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) low = mid + 1; else high = mid - 1;
}
return low;
}Watching it narrow
Here’s searchInsert([1, 3, 5, 6], 7), one step per row:
| low | high | mid | nums[mid] | Compared with 7 | Next |
|---|---|---|---|---|---|
| 0 | 3 | 1 | 3 | smaller | low = 2 |
| 2 | 3 | 2 | 5 | smaller | low = 3 |
| 3 | 3 | 3 | 6 | smaller | low = 4 |
| 4 | 3 | — | — | low > high: stop | return 4 |
Three steps for four elements; about 20 for a million.
Predict the output
What gets printed?
print(searchInsert([1, 3, 5, 6], 2), searchInsert([1, 3, 5, 6], 7))println("${searchInsert(intArrayOf(1, 3, 5, 6), 2)} ${searchInsert(intArrayOf(1, 3, 5, 6), 7)}")System.out.println(searchInsert(new int[] {1, 3, 5, 6}, 2) + " " + searchInsert(new int[] {1, 3, 5, 6}, 7));console.log(searchInsert([1, 3, 5, 6], 2), searchInsert([1, 3, 5, 6], 7));For 2: mid = 1 (3 is bigger, so high = 0), then mid = 0 (1 is smaller, so low = 1); the range is empty and low = 1, between 1 and 3. For 7: every middle element is smaller, so low walks to 4, one past the end, which is where 7 would be appended. Returning low gives the insertion point for free.
What the library returns
Predict the output
Searching for 4 in the sorted list [1, 3, 5], which isn't there. What gets printed?
print([1, 3, 5].firstIndex(where: { $0 >= 4 }))println(listOf(1, 3, 5).binarySearch(4))System.out.println(Arrays.binarySearch(new int[] {1, 3, 5}, 4));console.log([1, 3, 5].findIndex((x) => x >= 4));The Swift standard library has no binary search on Array, and firstIndex(where:) is a linear scan that returns an optional: Optional(2). For O(log n), write your own partitioningIndex (or use one from a package such as swift-algorithms), or keep data in a sorted structure.
binarySearch returns -(insertionPoint) - 1 when the element is missing: insertion point 2, so -3. The negative encoding means "not found" and still tells you where it belongs: -(result) - 1. With duplicates, it returns any matching index, not the first.
Arrays.binarySearch returns -(insertionPoint) - 1 when the key is missing: insertion point 2, so -3. Code that checks >= 0 is fine; code that uses the result as an index without checking gets a negative index. With duplicates, the returned index is unspecified, so use a lower-bound search when you need the first.
JavaScript has no built-in binary search. findIndex finds the first element >= 4, index 2, by a linear scan; it's correct, but O(n). For O(log n), write a lower-bound function like the one in this lesson.
Kotlin, Java
binarySearch (Kotlin) and Arrays.binarySearch / Collections.binarySearch (Java) return -(insertion point) - 1 when the key is missing, and any index among duplicates: use a lower bound when you need the first.
Swift
The standard library has no binary search on Array; firstIndex(where:) is linear. Write a partitioningIndex, or use swift-algorithms.
TypeScript
There’s no built-in binary search; findIndex is linear. And / doesn’t round: compute mid with Math.floor (or >>> 1 for array indices).
Check this part
What must be true about the data for binary search to work?
About how many steps does binary search need for 1,000,000 elements?
What does the standard library give you for an O(log n) search in a sorted
Array?What doeslistOf(1, 3, 5).binarySearch(4)return?What doesArrays.binarySearch(new int[] {1, 3, 5}, 4)return?What does the standard library give you for an O(log n) search in a sorted array?