Description
Locate target in a strictly increasing integer array. Return its zero-based index, or -1 if absent.
Solution
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] == target:
return middle
if nums[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1Examples
Example 1
- Input
[[-1,0,3,5,9,12],9]- Output
4
9 occurs at index 4.
Example 2
- Input
[[-1,0,3,5,9,12],2]- Output
-1
2 is missing.
Example 3
- Input
[[5],5]- Output
0
The single element matches.
Approach
Maintain inclusive left and right boundaries. Compare the midpoint with target and discard the half that cannot contain it. Stop when the interval is empty.
Time & space
O(log n) time and O(1) auxiliary space, where n is the array length.