Binary Search
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums.
If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with **O(log n)** runtime complexity.
Examples
nums = [-1,0,3,5,9,12], target = 94nums = [-1,0,3,5,9,12], target = 2-1Constraints
1 <= nums.length <= 10^4-10^4 < nums[i], target < 10^4All integers in nums are uniquenums is sorted in ascending order
💡 Hints
Hint 1
Compare the middle element with the target. If equal, you found it!
Hint 2
If the middle element is less than the target, search the right half. If greater, search the left half.
Algorithm Complexity
Official asymptotic Big-O runtime and auxiliary memory analysis
Classic binary search. Repeatedly halve the search space by comparing the middle element with the target. Each iteration eliminates half the remaining elements.
The search interval is halved on each iteration, executing at most ⌊log₂ n⌋ + 1 comparisons.
Iterative binary search uses constant O(1) auxiliary variables (left, right, mid).
🌍 Real-World Use Cases
Searching sorted inverted indexes to find documents containing a query term — binary search makes this O(log n) instead of O(n).
Finding the first and last products within a price range using binary search on a sorted price column.
🔍 Dry Run
Search for 23 in sorted array. Initialize left=0, right=7. Search space: entire array