Beginner LevelData Structures & Algorithms
How does Binary Search work and what are its prerequisites?
ā Interview Prompt: Explain Binary Search, its O(log N) time complexity, prerequisites, and how to implement it iteratively and recursively.
Binary Search repeatedly halves the search space by comparing the target to the middle element of a sorted array, achieving $O(\log N)$ time complexity.
Prerequisites:
1
The collection must be sorted.
2
Random access (O(1) index lookup) ā works best on arrays.
Algorithm:
1
Set
low = 0, high = n - 1.2
While
low <= high: compute mid = low + Math.floor((high - low) / 2).3
If
arr[mid] === target ā found.4
If
arr[mid] < target ā search right half (low = mid + 1).5
If
arr[mid] > target ā search left half (high = mid - 1).Code Implementation Example
typescript
// Iterative Binary Search ā O(log N) time, O(1) space
function binarySearch(arr: number[], target: number): number {
let low = 0, high = arr.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2); // avoids overflow
if (arr[mid] === target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1; // not found
}
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3š”Iterative Binary Search with overflow-safe midpoint calculation.
šÆ Interview Key Takeaway
Binary Search achieves O(log N) by halving the search space each step. Always use `low + (high - low) / 2` to prevent integer overflow.
#DSA#Binary Search#Searching#Algorithms#Beginner
Back to all Data Structures & Algorithms Questionsā