Given a sorted array nums of distinct integers and a value target, return the index of target if it is present. If it is not, return the index where it would be inserted so that the array stays sorted. The solution must be O(log n).
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i], target <= 10^4
- `nums` is sorted and has distinct values
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A linear scan finds the first element >= target in O(n). That "first element at least target" is exactly the lower bound, and the condition nums[i] >= target is false for a prefix of the array and true for the rest. Binary search finds the boundary between the false part and the true part in O(log n). If every element is smaller, the boundary is n, which is the correct insert position.
Algorithm
- Set
lo = 0andhi = n(the answer can ben). - While
lo < hi, takemid = lo + (hi - lo) / 2. - If
nums[mid] < target, the answer is to the right:lo = mid + 1. - Otherwise
midcould be the answer:hi = mid. - Return
lo.
O(log n)Space: O(1)lo < hi, hi = mid) is the base for many harder problems: first and last position, search on answer, and so on. Practise it until you can write it without off-by-one errors.class Solution: def searchInsert(self, nums: List[int], target: int) -> int: lo, hi = 0, len(nums) # answer lies in [0, n] while lo < hi: mid = (lo + hi) // 2 if nums[mid] < target: lo = mid + 1 # too small, go right else: hi = mid # mid may be the answer return lo