The problem
Given a sorted array of distinct integers nums and a target, return the index of target, or −1 if it is not there. It must run in O(log n) time.
Examples
01
- Input
nums = [-1, 0, 3, 5, 9, 12], target = 9
- Output
4
02
- Input
nums = [-1, 0, 3, 5, 9, 12], target = 2
- Output
-1
Constraints
- 1 ≤ nums.length ≤ 10⁴
- −10⁴ < nums[i], target < 10⁴
numsis sorted in ascending order, with no repeats.
The idea
Look at the middle element. Because the array is sorted, if it is smaller than the target, the target can only be to its right; if larger, only to its left. Either way half the array is ruled out with one comparison.
Keep the range still in play as lo..hi and repeat on the half that remains. Halving n repeatedly reaches 1 after about log₂ n steps — 14 steps for 10,000 elements.
- Time
- O(log n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def search(self, nums: List[int], target: int) -> int: lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[mid] < target: lo = mid + 1 # the target can only be to the right else: hi = mid - 1 # the target can only be to the left return -1