Binary Search
Classic binary search on a sorted array — the atomic primitive.
3 min read
binary-search
Problem#
Given a sorted ascending array nums and a target, return its index or -1.
Examples#
nums = [-1,0,3,5,9,12], target = 9→4nums = [-1,0,3,5,9,12], target = 2→-1
Constraints#
1 <= nums.length <= 10^4.
Approach#
lo, hi. While lo <= hi, compute mid (safe form lo + (hi - lo) / 2 to avoid overflow), compare to target, shrink the half.
Solution#
class Solution {public: int search(vector<int>& nums, int target) { int lo = 0, hi = nums.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; }};func search(nums []int, target int) int { lo, hi := 0, len(nums)-1 for lo <= hi { mid := lo + (hi-lo)/2 if nums[mid] == target { return mid } 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 - lo) // 2 if nums[mid] == target: return mid if nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1var search = function(nums, target) { let lo = 0, hi = nums.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) return mid; if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1;};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; if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; }}function search(nums: number[], target: number): number { let lo = 0, hi = nums.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) return mid; if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1;}Editorial#
The lo + (hi - lo) / 2 form prevents overflow on huge hi + lo. Inclusive lo <= hi plus exclusive updates (mid - 1, mid + 1) is the canonical “find exact match” template; for “first index with property”, use lo < hi plus hi = mid / lo = mid + 1.
Complexity#
- Time: O(log n).
- Space: O(1).
Concept revision#
Related#