Binary Search
You're given an array nums of distinct integers sorted in ascending order, and an integer target. Return the 0-based index where target appears in nums, or -1 if it does not appear. Your algorithm must run in O(log n) time, so checking the elements one by one is not allowed.
Examples
nums = [-1,0,3,5,9,12], target = 9 returns 4
9 is the fifth element, which is index 4 when counting from 0.
nums = [-1,0,3,5,9,12], target = 2 returns -1
2 would sit between 0 and 3, but it isn't in the array, so the answer is -1.
Constraints
- 1 <= nums.length <= 10^4
- -10^4 < nums[i], target < 10^4
- All the integers in nums are unique.
- nums is sorted in ascending order.
Hints
The array is sorted. After comparing target with a single element, how much of the array can you rule out?
Binary search: compare against the middle element and throw away the half that can't contain target.
Set lo = 0 and hi = n - 1. While lo <= hi, take mid = lo + (hi - lo) / 2. Return mid if nums[mid] == target; if nums[mid] < target set lo = mid + 1, else set hi = mid - 1. Return -1 after the loop.
Drill This: Your Approach First
Approach
Keep a range [lo, hi] that must contain target if it exists at all. Compare target with the middle element: on a match return mid, if the middle is smaller everything up to mid is too small so set lo = mid + 1, otherwise set hi = mid - 1. The range halves every step, and once lo passes hi the target is not there.
Time
O(log n)
Space
O(1)
Pitfall
Solutions
class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
}from typing import List
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
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1