Binary Search
Find a target value in a strictly increasing array using binary search.
Work through the cases
3 examplesInput notation
Space-separated integers on line 1. Target on line 2.Expected result
Its zero-based index, or -1.Case 1
Input
-3 0 5 9 5
Expected output
2
Case 2
Input
1 4 7 2
Expected output
-1
Case 3
Input
5 5
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Search target in a strictly increasing array. n ≤ 10^4 would allow a scan, but each comparison can discard half of a sorted range. If nums[mid] ≥ target, the answer is not to the right, so r moves to mid; otherwise it lies past mid, so l becomes mid+1. When l=r we sit on the first value that is not smaller than the target, then compare once. Time O(log n), extra space O(1).
We define the left boundary l=0 and the right boundary r=n-1 for binary search.
In each iteration, we calculate the middle position mid=(l+r)/2, then compare the size of nums[mid] and target.
- If nums[mid] ≥ target, it means target is in the left half, so we move the right boundary r to mid; - Otherwise, it means target is in the right half, so we move the left boundary l to mid+1.
The loop ends when l<r, at this point nums[l] is the target value we are looking for. If nums[l]=target, return l; otherwise, return -1.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l] == target ? l : -1;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.