This content originally appeared on flaviocopes.com and was authored by flaviocopes.com
Binary search assumes the array (or any other data structure) you are searching in is ordered.
We start with the array, and the item we need to search for.
We look at the middle of the array. We take the number of elements, and we divide it by 2. Imagine we have a part of the array on the left, and the other part on the right.
If the item we have is lower than the one we’re looking for, then it must be in the right part, so we can completely discard the part on the right.
Then we perform the same action, dividing the right part of the array in 2, looking at the middle item, and we throw away part of the array.
In the end, you will get the item (or you will return null if the item is not found).
In the end, if the array had 8 items, we find the item in at most 4 steps.
If the array had 32 items, we have a maximum of 6 steps in the worst case. Compared to 32 in linear search, that’s a huge optimization!
Binary search has O(log n) complexity.
Here’s a possible implementation of it:
const binarySearch = (list, item) => {
let low = 0
let high = list.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
const guess = list[mid]
if (guess === item) {
return mid
}
if (guess > item) {
high = mid - 1
} else {
low = mid + 1
}
}
return null //if not found
}
How does this work? We get the list array, and the item value we’re looking for. Then we initialize the low value at 0 initially, and the high value to the last index in the list. We first look at the middle item, and if it’s what we’re looking for we return it, and we’re done. If not, we set the low or high values to only look at the left or right part of the array, and we repeat the process until we find the item.
We return the index of the item in the array:
console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4
We return null if the element is not found:
console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null
This content originally appeared on flaviocopes.com and was authored by flaviocopes.com
flaviocopes.com | Sciencx (2020-11-21T05:00:00+00:00) JavaScript Algorithms: Binary Search. Retrieved from https://www.scien.cx/2020/11/21/javascript-algorithms-binary-search/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.