JavaScript Algorithms: Binary Search
New Courses Coming Soon
Join the waiting lists
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
Here is how can I help you:
- COURSES where I teach everything I know
- CODING BOOTCAMP cohort course - next edition in 2025
- THE VALLEY OF CODE your web development manual
- BOOKS 16 coding ebooks you can download for free on JS Python C PHP and lots more
- Interesting links collection
- Follow me on X