You are given an array nums sorted in increasing order with no duplicates, and a value target. Return the index of target in nums, or -1 if it is not there. Your algorithm must run in O(log n) time.
Example 1
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Example 2
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Constraints
- 1 <= nums.length <= 10^4
- -10^4 < nums[i], target < 10^4
- All values are unique
- `nums` is sorted in ascending order
Hints
Frequently asked at: Microsoft, Amazon, Apple, TCS, Infosys
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Scanning every element costs O(n) and ignores that the array is sorted. Comparing target with the middle element tells us which half can contain it, so we throw away half the array each step. After at most log2(n) steps the range is empty or we found the target.
Algorithm
- Set
lo = 0,hi = n - 1. - While
lo <= hi, computemid = lo + (hi - lo) / 2. - If
nums[mid] == target, returnmid. - If
nums[mid] < target, setlo = mid + 1, else sethi = mid - 1. - Return
-1when the loop ends.
Time:
O(log n)Space: O(1)Interview tip: Write
mid = lo + (hi - lo) / 2 rather than (lo + hi) / 2 in Java and C++. With large indices the sum can overflow an int, and interviewers love to ask about it.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 # answer is on the right else: hi = mid - 1 # answer is on the left return -1Ctrl + Enter runs the examples