Q5: Binary Search
Search for a target value within a sorted array using the divide-and-conquer strategy, reducing the search space by half in each iteration.
Binary Search Implementation
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
console.log(binarySearch([-1, 0, 3, 5, 9, 12], 9)); // 4💡 Calculates mid index safely. If target is larger than nums[mid], discards the left half; otherwise discards the right half.
Key Takeaways
- Requires a sorted array input.
- Achieves logarithmic O(log n) time complexity.
Knowledge Check
Why is Math.floor(left + (right - left) / 2) preferred over Math.floor((left + right) / 2)?