Binary search is a powerful algorithm used to efficiently find the position of a target value within a sorted array or list. Its effectiveness lies in its ability to eliminate half of the remaining elements in each step, resulting in a logarithmic time complexity of O(log n), where n is the number of elements in the array.
Let’s break down how binary search works and provide a practical example in JavaScript.
How Binary Search Works
1 – Initial Setup:
- Start with a sorted array.
- Set two pointers,
low
andhigh
, to the first and last indices of the array.
2 – Middle Element:
- Find the middle element of the array:
mid = Math.floor((low + high) / 2)
.
3 – Comparison:
- Compare the middle element with the target value.
4 – Three Possible Cases:
- If the middle element is equal to the target value, the search is successful.
- If the middle element is greater than the target, update
high
tomid - 1
and search in the left half. - If the middle element is less than the target, update
low
tomid + 1
and search in the right half.
5 – Repeat:
- Repeat steps 2-4 until the target value is found or
low
exceedshigh
.
6 – Termination:
- If
low
is greater thanhigh
, the target value is not in the array.
Example in JavaScript
Let’s implement a binary search algorithm in JavaScript:
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid; // Target found, return the index
} else if (arr[mid] > target) {
high = mid - 1; // Search in the left half
} else {
low = mid + 1; // Search in the right half
}
}
return -1; // Target not found
}
// Example usage:
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const targetValue = 7;
const result = binarySearch(sortedArray, targetValue);
if (result !== -1) {
console.log(`Target ${targetValue} found at index ${result}.`);
} else {
console.log(`Target ${targetValue} not found in the array.`);
}
In this example, we use a binarySearch
function to find the index of a target value in a sorted array. The function returns the index if the target is found and -1 otherwise.
Feel free to use this binary search algorithm in your projects when dealing with sorted data. Its efficiency makes it a valuable tool, especially for large datasets. Happy coding!
Leave a Reply