Mastering Binary Search: The Efficient Way to Find Elements in a Sorted Array
Binary Search is a powerful algorithm based on the divide-and-conquer approach, allowing us to search elements efficiently in a sorted array. Compared to a linear search, which has a time complexity of O(n), binary search significantly reduces the search time to O(log n) by halving the search space at each step.
Key Features:
- Works only on sorted arrays.
- Much faster than linear search due to its logarithmic time complexity.
- Splits the search space in half with each iteration, narrowing down the target efficiently.
function binarySearch(list, item, left, right) {
let mid = Math.floor((left + right) / 2)
if (left > right) {
return false
}
// If the midpoint is the item we're looking for, return true.
if (list[mid] == item) {
return true;
} else if (item < list[mid]) {
// If the item is smaller than the midpoint, search the left half.
return binarySearch(list, item, left, mid - 1)
} else {
// Otherwise, search the right half
return binarySearch(list, item, mid + 1, right)
}
}
let list=[1,2,3,5,6,7,8,9];
console.log(binarySearch(list,10,0,list.length-1))
Why is Binary Search Fast?
Because it halves the search space with each comparison. For an array of 1000 elements, instead of checking each one, binary search only takes about 10 checks (logโ(1000) โ 10), making it much faster for large datasets.
Example Walkthrough:
Let's say you want to search for the number 5 in the array [1, 2, 3, 5, 6, 7, 8, 9].
Step 1: Start with left = 0, right = 7. Calculate mid = (0 + 7) / 2 = 3.
list[mid] is 5, which is our target, so return true.
This simple, efficient process allows us to find the element quickly.
Feel free to drop your thoughts or suggestions on how to improve the algorithm further! ๐
Top comments (0)