In this post, I’ll compare linear search and binary search algorithms. You’ll see pseudocode for each algorithm, along with examples and a step-by-step guide to implementing each.
Introduction
As a programmer, you want to find the best solution to a problem so that your code is not only correct but efficient. Choosing a suboptimal algorithm could mean a longer completion time, increased code complexity, or worse a program that crashes. You may have used a search algorithm to locate items in a collection of data. The JavaScript language has several methods, like find, to locate items in an array. However, these methods use linear search. A linear search algorithm starts at the beginning of a list and compares each element with the search value until it is found. This is fine when you have a small number of elements. But when you are searching large lists that have thousands or millions of elements you need a better way to locate items. This is a when you would use binary search. In this tutorial, I will explain how binary search works and how to implement the algorithm in JavaScript. First, we will review the linear search algorithm.
Linear Search
We will begin by explaining how to implement linear search in JavaScript. We will create a function called linearSearch that accepts a value that is an integer or string and an array as parameters. The function will search every element in the array for the value and return the position of the value in the array if it is found. If the value is not in the array, it will return -1. For example, calling linearSearch(1, [3, 4, 2, 1, 5]) would return 3 and calling linearSearch(0, [3, 4, 2, 1, 5]) would return -1.
Here’s some pseudocode for our function:
Set found to false
Set position to −1
Set index to 0
while found is false and index < number of elements
if list[index] is equal to search value
Set found to true
Set position to index
else Add 1 to index
return position
JavaScript Implementation of Linear Search
Here is a JavaScript implementation of the linear search algorithm:
function linearSearch(value, list) {
let found = false;
let position = -1;
let index = 0;
while(!found && index < list.length) {
if(list[index] == value) {
found = true;
position = index;
} else {
index += 1;
}
}
return position;
}
It is important to note that the linear search algorithm does not need to use a sorted list. Also, the algorithm can be customized for use in different scenarios like searching for an array of objects by key. If you have an array of customer data that includes keys for the first and last name, you could test if the array has a customer with a specified first name. In that case, instead of checking if list[index] is equal to our search value, you would check for list[index].first.
In the example above, I used the linearSearch function on an array with 5 elements. In the worst case, when the search value is not in the list or is at the end of the list, the function would have to make 5 comparisons. Because our array is so small there is no need to optimize by using a different algorithm. However, up to a certain point, it is no longer efficient to use a linear search algorithm and that is when using a binary search algorithm would be better.
Binary Search
Imagine you are playing a number guessing game. You are asked to guess a number between 1 and 100. If your number is too high or too low you will get a hint. What would your strategy be? Would you choose numbers randomly? Would you start with 1, then 2, and so on until you guessed correctly? Even if you had unlimited guesses you want to make the correct guess in as few tries as possible. Therefore, you might start with guessing 50. If the number is higher you could guess 75. If it is lower, then that means the number is between 50 and 75 and you would choose a number that's in the middle. You would go on like this until you arrived at the correct number. This is similar to how binary search works.
Unlike linear search, binary search uses a sorted list. To search for a value, you first compare the value to the middle element of the list. If they are equal, the search value has been found. If the search value is greater than the middle element, you search the top half of the data. You then compare the middle element of this section to the search value. Alternatively, if the item is less than the middle element, you search the bottom half of the list and compare its middle value. The list is repeatedly divided in half until the element is found or there are no more items to search.
To search for 9 in the list:
1 2 3 4 5 6 7 8 9 10
We first find the middle element. This is the element at position Math.floor((first + last)/2) where first is the first index, and last is the last index. We choose to round down so that in the case the result is a fraction it becomes a whole number. The middle element in this list is 5. Our search value 9 is greater than 5 so we search the list:
6 7 8 9 10
The middle element of this portion is 8. Nine is greater than 8 so we search the list:
9 10
The middle element is 9, so we can stop our search here.
Here's some pseudo code that expresses the above algorithm for binary search:
Set first to 0
Set last to the last index in the list
Set found to false
Set position to −1
while found is false and first is less than or equal to last
Set middle to the index halfway between first and last
if list[middle] equals the desired value
Set found to true
Set position to middle
else if list[middle] is greater than the desired value
Set last to middle − 1
else
Set first to middle + 1
return position
JavaScript Implementation of Binary Search
Now let's code the binary search algorithm in JavaScript!
We'll create a function, binarySearch, that accepts a value and an array as parameters. It will return the index where the value occurs in the list if found. If the value is not found it returns -1. This is our implementation written in JavaScript:
function binarySearch(value, list) {
let first = 0; //left endpoint
let last = list.length - 1; //right endpoint
let position = -1;
let found = false;
let middle;
while (found === false && first <= last) {
middle = Math.floor((first + last)/2);
if (list[middle] == value) {
found = true;
position = middle;
} else if (list[middle] > value) { //if in lower half
last = middle - 1;
} else { //in in upper half
first = middle + 1;
}
}
return position;
}
Conclusion
In this tutorial, we saw how to implement a linear search and a binary search algorithm. The linear search algorithm is simpler and doesn't require a sorted array. However, it is inefficient to use with larger arrays. In the worst case, the algorithm would have to search all elements making n comparison (where n is the number of elements).
The binary search algorithm, on the other hand, requires you sort the array first and is more complicated to implement. However, it is more efficient even when considering the cost of sorting. For example, an array with 10 elements would make at most 4 comparisons for a binary search vs 10 for a linear search—not such a big improvement. However, for an array with 1,000,000 elements the worst case in binary search is only 20 comparisons. That's a huge improvement over linear search!
Knowing how to use binary search isn't just something to practice for an interview question. It's a practical skill that can make your code work much more efficiently.
Powered by WPeMatico
