02. Binary Search
Given a sorted array of integers nums and a target, write a function to search for target in nums in $O(\log n)$ time.
How It Works & Algorithmic Design
Binary Search uses Divide and Conquer on sorted arrays:
- Pointers: Set
left = 0,right = nums.length - 1. - Mid Calculation: Compute
mid = Math.floor((left + right) / 2)(orleft + Math.floor((right - left) / 2)to prevent overflow in fixed integer types). - Halving Condition:
- If
nums[mid] === target, returnmid. - If
nums[mid] < target, discard left half:left = mid + 1. - If
nums[mid] > target, discard right half:right = mid - 1.
- If
- Failure: Return
-1ifleft > right.
Why This Approach Works Best
Halving the search space each iteration reduces search time from linear $O(n)$ to logarithmic $O(\log n)$ time complexity.
Example Walkthrough
Input:
nums = [-1, 0, 3, 5, 9, 12], target = 9Sorted array input.
Step 1:
left=0, right=5 -> mid=2 (nums[2]=3). 3 < 9 -> left=3.Discards left half.
Step 2:
left=3, right=5 -> mid=4 (nums[4]=9). Match found!Target identified at index 4.
Output:
4Index of target value 9.
Answer: Binary Search implementation
function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}💡 Halves the search range in each iteration using two boundary pointers.
Key Takeaways
- Binary search requires the input array to be pre-sorted.
- Use
left + (right - left) / 2to avoid integer overflow issues in languages like C++/Java. - Logarithmic time complexity $O(\log n)$ enables ultra-fast searching across large datasets.