You are given a list nums of different integers, sorted from smallest to largest, and an
integer target. Return the index of target in nums (counting from 0), or -1 if it isn't
there.
Your solution should take O(log n) time.
Example 1
- Input
- nums = [-4, 0, 3, 8, 12, 20], target = 8
- Output
- 3
Example 2
- Input
- nums = [-4, 0, 3, 8, 12, 20], target = 5
- Output
- -1
5 would sit between 3 and 8, but it isn't there.
Constraints
numsholds 1 to 10⁴ numbers, all different, in increasing order.- Every number, and
target, is between −10⁴ and 10⁴.
Show the pattern
Binary search
The list is sorted, so one comparison with the middle number tells you which half the target must be in. Halving the range at every step finds it in O(log n).
See binary search in a visualiserShow the approach
Keep lo = 0 and hi = n − 1, the range where target could be. While lo ≤ hi, look at
mid = (lo + hi) // 2. If nums[mid] is the target, return mid. If it is smaller, the target
can only be to its right: set lo = mid + 1. Otherwise it can only be to its left: set
hi = mid − 1. If the range runs out, return -1.
Time: O(log n) · Space: O(1)
Brush up firstBinary Search visualiser