Theory
Binary Search works on sorted data. It repeatedly divides the search range into two halves. If the target is smaller than the middle element, the left half is searched. Otherwise, the right half is searched. Its time complexity is O(log n).
Example
const numbers = [10, 20, 30, 40, 50];
const target = 40;
let left = 0;
let right = numbers.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (numbers[mid] === target) {
console.log("Found:", mid);
break;
}
if (numbers[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
Expected Output
Found: 3
Practice
Implement binary search for a sorted array.
Interview Questions
- What is binary search?
- Why must the data be sorted?
- What is the time complexity of binary search?
- How does binary search reduce the search space?