When a list is sorted, you never need to look at every element. Comparing against the middle tells you which half the target must be in, so each step halves the work: O(log n) instead of O(n).
Given a sorted list of distinct integers nums and an integer target, return the index of target in nums, or -1 if it is not present.
Examples
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Constraints
0 <= len(nums) <= 10**4- All elements of
numsare distinct and sorted ascending. - Aim for O(log n) time. Do not use
list.index()or thebisectmodule.
Goals
- Maintain lo and hi bounds that always contain the answer if it exists
- Compute the midpoint and discard half of the search space each step
- Write a loop condition and updates that cannot loop forever