Binary Search
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
Example:
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.
1 | class Solution { |
Key Points:
while(start < end)
: when start and end are overlapped each other, break. At this moment, we can return start or end. But it is different when we need to return the index before or after the target(see point 3).int mid = start + (end - start) / 2
: in order to avoid overflow ofstart + end
, we need to do a little trick here.while loop
: in the while loop, there are two different needs:
- return the index of the target: as the example above.
- return the one before(example below)/after the target:
Search Insert PositionHere, we need to use1
2
3
4
5
6
7
8
9
10while(start <= end) {
int mid = start + (end - start) / 2;
if(A[mid] == target) {
return mid;
} else if(A[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}while(start <= end)
so that when we break the loop, two pointers are at two different(but neighbored) positions. Besides, if we want to return the one before the index, we returnstart
, otherwise we returnend
.