Problem
Given a sorted array of integers and a target, return the index of target. Return -1 if not found. Must run in O(log n) time.
Example
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4Solution
Classic binary search. Compare target with middle element. Eliminate half each iteration.
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Complexity
- Time: O(log n)
- Space: O(1)
Explanation
Use mid = left + (right – left) / 2 instead of (left + right) / 2 to avoid integer overflow on huge arrays.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?