I’ve recently started reading A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow and the gentle introduction uses linear search and binary search as simple algorithms that serve as good examples to compare and contrast performance. Let me see if I can explain what I learned!
Unordered vs Ordered Arrays
Before we get into the search algorithms, let’s be absolutely clear about what we mean by an unordered array and an ordered one.
An unordered array is where the items within the array are not in a specific order, i.e. numerical.
// unordered array
let array = [9, 4, 12, 3, 16]An ordered array is where the items are in a specific order.
// ordered array (numerical order)
let array = [3, 4, 9, 12, 16]As you can see, the numbers are in ascending order.
Creating an Ordered Array in Javascript
It’s worth us noting that binary search will only work with ordered arrays and not unordered arrays.
However, if you’re in a situation where you have a large unordered numerical array but want to benefit from binary search, here’s how to convert it using Array.sort():
// ordering an unordered array
let numbers = [9, 4, 12, 3, 16]
numbers.sort((a, b) => a - b);
console.log(numbers)
// expected output: [3, 4, 9, 12, 16]
Searching for an Item in an Array
Now that we have our ordered array, we need a way to find a specific element in that array (if present). To do that, we’ll compare two methods; linear search and binary search.
Linear Search
The linear search algorithm is pretty straightforward; it checks each item in the array, one by one, in the order the items are in. It stops once it either;
- Finds a matching item
- Finds an item value larger than the searched-for value
- Reaches the end of the array
While it being straightforward is a benefit, it also has a drawback in that it’s not particularly performant when it comes to larger arrays. If you have an array of 1,000 items, the linear search algorithm will need to run through up to 1,000 steps.
In big O notation, it would be represented with O(N), where N represents the number of items in the array.
Here we’re not necessarily looking to optimise the number of lines of code written but instead the underlying performance of the function. Consider the fact that an array could hold many thousands of items; it becomes less important that the function fits on the fewest lines of code and more important that it runs efficiently with the fewest steps.
Linear Search Example
let numbers = [3, 4, 9, 12, 16];
// Linear search - the explicit way
function linearSearch(array, searchValue) {
for (let index = 0; index <= numbers.length; index++) {
if (array[index] === searchValue) {
return index;
} else if (index > searchValue) {
return
}
}
}
console.log(linearSearch(numbers, 12)); // returns 3
// Linear search - the quick way using the native indexOf method
console.log(numbers.indexOf(12)) // returns 3Binary Search
While linear search takes the simple approach of checking each item in the array in their order, binary search takes a smarter approach that can be significantly quicker.
Binary search works by essentially splitting the array in two and repeatedly discarding the half which is either too low or too high to match the searched-for value.
You start by taking the full array and checking the value of the middle-most item. If it’s higher than the searched-for value then you discard the second half of the array entirely and focus instead on the first half, checking the middle value of this new selection once again. And so on.
The speed comes from the ability to discard half of the remaining items at each step in the algorithm. This means that if you were to be working with an array that’s double the size of your existing one, you only need one more additional step in the algorithm.
In Big O Notation, this is represented by O(log n).
Therefore, the more items in the array the larger the improvement will be in going from linear search to binary search.
Binary Search Example
let numbers = [3, 4, 9, 12, 16];
// Binary search
function binarySearch(array, searchValue) {
let lower = 0;
let upper = numbers.length - 1;
while (lower <= upper) {
let middle = Math.floor((upper + lower) / 2)
let middleValue = array[middle]
if (middleValue == searchValue) {
return middle
} else if (searchValue < middleValue) {
upper = middle - 1
} else if (searchValue > middleValue) {
lower = middle + 1
} else {
return
}
}
}
console.log(binarySearch(numbers, 12)); // returns 3
Comparison Example
To put these two algorithms to the test, how about a head-to-head?
In the example below, I’ve made the array significantly larger – 1,000 items – in order to make the difference between the two a lot clearer.
Click the ‘Result’ tab to see the difference in steps.
As you can see, there is a huge difference in the number of steps to reach the same result. Remember, this is just an array of 1,000 items. There may be situations where you’re dealing with significantly more and for binary search, this may mean just a few additional steps.