What's your default method when you search for an item in an array? You could be familiar with the popular indexOf method or if you are versed in the functional programming paradigm, then find or findIndex might ring a bell. What if one day these convenient array methods are stripped away from you? how would you implement a solution yourself? Today we will talk about how to natively implement searching algorithms of on our own.
Linear Search
This is probably the most naive approach you can take, almost a brute-force approach. This algorithm simply loops through a given array from the beginning and compare each value with the provided matching value. Let's create a function called linearSearch to return the first index of the match if there is one, otherwise, return false.
linearSearch([1,2,3,4,5], 5)
function linearSearch(arr, match) {
for(let i=0; i<arr.length; i++) {
if(arr[i] === match) {
return i;
}
}
return false;
}
Pretty straightforward right?
One advantage of using linear search algorithm is that the passed-in array doesn't have to be sorted. The array could look chaotic like [3,1,4,2,5] and it would still work. Actually, we just basically implemented Array.indexOf method 😄
What's the disadvantage? Well, imagine if the array contains thousands of values and our match happens to be positioned as the very last index. Even worse, what if there wasn't any match at all? It's very taxing for our computers and time consuming to iterate through a large set of numbers and make calculations. I think we can do better than this! By the way, because we are using a single loop, it's O(n) complex.
Binary Search
In binary search, we are looking for our match by diving the search interval in half. Think of breaking our passed-in array into subarrays by half of its length repeatedly until it finds a match. It would be very efficient! So efficient that time complexity is only O(log n). Here is how it works. If the value in the middle is less than the match, it means that the matching value is found in the latter half where its values are greater than the middle value (That is, if there is any match). If the value in the middle is greater than the match, then we can search again in the first half of the array. Rinse and repeat, divide and conquer! Let's now explain with some codes :)
function binarySearch(arr, match) {
let start = 0; // first index
let end = arr.length - 1; // last index
let middle = (start + end) / 2; // middle index
}
Here is our starting code, which is pretty straightforward. Passing in [1,2,3,4,5] as arr results in '(0 + 4) / 2 = 2' and at index 2 is where our middle number is. One pitfall to look out for though! Our middle will only be the correct integer index if the array has odd length. To account for even number length array, let's modify the 3rd line a little bit.
let start = 0;
let end = arr.length - 1;
let middle = Math.floor((start + end) / 2);
Without Math.floor, passing in [1,2,3,4] results in 1.5. Using it will round down the number to 1 so middle is pointing at number 2 in the array. Now our bread and butter of our algorithm.
function binarySearch(arr, match) {
let start = 0;
let end = arr.length - 1;
let middle = Math.floor((start + end) / 2);
while(arr[middle] !== match) {
if(match > arr[middle]) {
start = middle + 1;
} else {
end = middle - 1;
}
middle = Math.floor((start + end) / 2);
}
return middle;
}
We created a while loop to continuously repeat some actions until the middle value equals our match. Inside the loop, if our match is greater than the current middle value, it means our match can be found in the 2nd half of the array. So we could safely exclude the first half by moving our start index 1 greater than the middle index. If our match is smaller, then our match belongs to the first half and bring our end index 1 less than the middle index. This means that our array has to be a sorted array.
We just shrunk our array in half so we need to reset our middle value again with a modified start or end. We repeat until we find the match then return its index.
Great! but what if there is no match in the array... Our condition in the while loop will spin forever and cause an infinite loop. Here is the fix.
function binarySearch(arr, match) {
let start = 0;
let end = arr.length - 1;
let middle = Math.floor((start + end) / 2);
while(arr[middle] !== match && start <= end) {
if(match > arr[middle]) {
start = middle + 1;
} else {
end = middle - 1;
}
middle = Math.floor((start + end) / 2);
}
if(arr[middle] === match) {
return middle;
}
return false;
}
What has changed? The while loop condition and our return statement! In addition to keep running the loop if the middle value doesn't find our match, we check to see if start is less than or equal to end so that if start is greater than end, the loop can say 'There is no match in the array!' and exit. Imagine a scenario we pass [1,3,5] and 6 as the match. We first start with index 1 and value 3 as our middle and because 6 is greater than 3, start becomes index 2 which is equal to end and thus middle becomes 2 as well. The loop runs again this time to check if middle value equals the match, it doesn't so it will move start or end by 1 in a direction so now in the next iteration, start is greater than end thus the loop won't execute.
If we found the match in the array in the end, return the index! Otherwise, return false.
Summary
Linear search is intuitive to write and logic about and we don't have to pass in an array that is sorted. But it's slow. BinarySearch is a lot quicker but is a bit more challenging to logic about and the passed-in array needs to be sorted. Therefore, go with the binary search algorithm if you are working with a large data set!!😉 Thank you for reading y'all!
Top comments (4)
Also you can use better searching algorithms if you know what sort of distribution in the sorted array your data lies.
en.m.wikipedia.org/wiki/Exponentia...
en.m.wikipedia.org/wiki/Fibonacci_...
Useful in some situations embedded situations I'm looking at you :)
Cool! Never seen these search algorithms methods before :) thanks for sharing.
Good post for beginners!
Most searches outside of linear require the data to be sorted.
Which requires an efficient sorting algorithm, which could be a good follow up.
Efficient and appropriate is the best combination.
Not going to use radix sort for everything :)