In This Post, I will try to cover search in javascript. It is not going to be any complicated searching algorithm but rather simpler algorithms that are commonly used. Javascript provides several search methods like indexOf includes find and many others. Our Focus here would be on how to implement our version of these methods.
We will cover two algorithms in this post Linear Search and Binary Search.
First thing first the coding environment. You Can use any editor you want local or online. But here I will be using google chrome snippets. Our code will be plain javascript therefore we don't need any fancy environment. If you want to follow along head on to google chrome's dev tools ctrl + shift + I . Click on the sources tab and from the left navigator select snippets. Create new snippets and name it linearSearch.
we can use ctrl + Enter to run the code as you can see at the bottom of the above image. Now that that's out of the way lets begin.
Linear Search
All the javascript search methods like find, indexOf etc. are using Linear Search. This is the simplest way of searching. Given an array, we look at every element to find what we are looking for. We check one item at a time starting from the beginning of the array or end of the array. Let's say we have a list
const list = [12, 45, 48, 5, 451, 2,34 ,43,54,66 ]
we want to search for 2. The data is not sorted in this array so the best approach would be to loop through every item in the array and check if the current iteration is equal to 2
pretty Simple Right.
Lets Code this. How are we going to approach this? Let's Break it down into pieces.
- We will write a function named you guessed it
linearSearch. That function will accept two arguments. an array and a value. - Inside that function, we will loop through the entire array and check if current item is equal to value.
- If The value is found we will return the
indexof that value otherwise we will returnfalseor-1
Step One
A function that will accept two arguments
var linearSearch = (list,value)=>{}
If you are using google chrome Snippets and want to use const or let Please use let because if you use const you cannot redeclare the variable and google chrome console will through an error.
Step Two
First, create a list and value. Two arguments our function needs.
let linearSearch = (list,value)=>{}
var list = [12, 45, 48, 5, 451, 2,34 ,43,54,66 ]
var value = 2;
linearSearch(list , value) // call the function with arguments
Now we will implement the Logic.
let linearSearch = (list,value)=>{
for (let i = 0; i < list.length; i++) {
if (list[i] === value) {
return i;
}
}
return -1;
}
var list = [12, 45, 48, 5, 451, 2,34 ,43,54,66 ]
var value = 2;
linearSearch(list , value) // result should 5
Let's try to understand what is going on inside the loop
We can refer to an element inside an array as arr[0] this will give us the first value and arr[1] will give us the second value and so on.
Let see this in action
in our loop i will be incremented from 0 to 9. on each iteration we will get the value from list of that index list[i] and compare it with our argument value;
we can confirm this with bydebugger in our snippet
I clicked on line 4 to add debugger. You can see step by step iteration by pressing f9. The above step is the step where we find our match( step 6 with i = 5). You can see in the Block panel (left side) all the variables we have access to.
I would Suggest you play around with debugger to see the call Stack Block local and global scope
We are returning -1 outside of the loop if we don't find the match.
NOTE: Return -1 outside of the loop
Final Step
Let's check the condition where value is not in list
Great! It is working
*Keep that in mind that array can be sorted or unsorted in linear search * The best-case scenario is we will find the item we are looking for immediately and worst-case scenario is that our required item is the last item in the array. For small arrays, it works fine but for large arrays performance might not be ideal.
Let's Move on to Binary Search Now.
Binary Search
Binary search is a much faster algorithm because of the way it works. At any given point it eliminates half of the array.
But The only caveat is it only works on Sorted arrays.
How it works
Because the array is sorted we pick the middle point of the array. After setting the middle point we will check if the value we are looking for is greater then or less then our midpoint. If The Value is greater then the midpoint that means our value is on the right side of our midpoint so we don't need left (or less then side) so we ditch the left side and look in the right side. We will keep doing that until we find our value.
confused.?
Let's try to visualize this. Define our array first.
let list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30];
let's say we are looking for 20
We Need three points left , right , middle
left = 2
right = 30
mid point could be 14 or 16. I am going to pick 14
our mid point is 14 and our value is 20 so we will eliminate the left side which is from 2 to 14
our arrays would look like this now
let list = [16, 18, 20, 22, 24, 26, 28, 30];
our next mid point will be our value between 22 and 24 we will pick 22 and left = 16, right = 30
From our mid (22), is our value (20) grater or less? It's less than right.? so this time we eliminate items on the right side
our new array should look like this
let list = [16, 18, 20, 22];
mid point 18 left 16 right 22.
our value is greater than 18
let list = [20, 22];
mid point === 20
Mid point === value
In Just Three loops we have found our Value. If We do the same with linear search it would take around 10 loops to find value 20
binary search is much faster. But it only works in sorted data.
Lets code this. So How Should we approach this? Let's think this through.
- We will write a function that accepts two arguments a sorted array and a value.
- we need Left and Right pointers. So We will create variable
leftwhose value will be the first item in our array and the right variable whose value will be the last item in the array- we also need a middle point which we can get from an average of
leftandright
- we also need a middle point which we can get from an average of
- we will loop until the mid === value
- if we find the value we will return the index if that value
- if the value is too small we will move left pointer up to the previous mid point and recalculate the mid point
- if the value is too large we will move the right pointer down to the mid point and so on and on until we find our value.
- If Value Not found we will return
falseor-1
Hwww. That is a lot but let's get through this step by step.
Let's define a function, a sorted array, and a value.
let BinarySearch = (list,val)=>{}
let list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]
let val = 20;
We Need Three pointers here. left, right, mid
let left = 0;
let right = list.length - 1;
let mid = Math.floor((left + right) / 2);
left is 0 because arrays are zero index so the first item in the array will at 0 index.
right again because arrays are zero index so to get the last item we will subtract 1 from its length.
mid to calculate average we use this formula (left + right) / 2. we don't want decimal number so we use javascript built in method Math.floor(). You can also use Math.ceil()
to loop through the array we will use while loop
let BinarySearch = (list,val)=>{
let left = 0;
let right = list.length - 1;
let mid = Math.floor((left + right) / 2);
while (list[mid] !== val && left <= right) {
if (val < list[mid]) {
right = mid - 1
} else {
left = mid + 1
}
mid = Math.floor((left + right) / 2);
}
if (list[mid] === val) {
return mid;
} else {
return -1
}
}
;
let list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]
let val = 20;
// should return 9
BinarySearch(list, val);
Scary huh.? Let's Walk this through
First, we will try to understand while loop
while (list[mid] !== val) {
if (val < list[mid]) {
right = mid - 1
} else {
left = mid + 1
}
mid = Math.floor((left + right) / 2);
}
in first line we are saying loop until the current iteration item is not equal to value.
inside the loop we checking our conditions
if our value (20) is less then the current iteration item that means we need to move the right end towards the middle.
otherwise the value is greater then current iteration item so our left should move towards the middle.
on each iteration, we are recalculating our middle point. The Above code will work fine until we provide false value.
in case of false or no match, we will be in infinite loop. So We need to handle it appropriately.
First of all we want the code to run until left is greater than or equal to right.
So Modify the above code.
while (list[mid] !== val && left <= right) { // <-- modified
if (val < list[mid]) {
right = mid - 1
} else {
left = mid + 1
}
mid = Math.floor((left + right) / 2);
}
And Check if our mid point is equal to the value we are looking for then return mid otherwise return -1
while (list[mid] !== val && left <= right) {
if (val < list[mid]) {
right = mid - 1
} else {
left = mid + 1
}
mid = Math.floor((left + right) / 2);
}
// add this code
if (list[mid] === val) {
return mid;
} else {
return -1
}
let's Test this out
With False value
Conclusion
Both Binary Search and Linear Search has there own pros and cons. Linear Search loop through every item of the array which in large arrays would be less performant. But it works on all kinds of arrays. Binary Search on the other hand can be a lot faster but the downside to this algorithm is that it only works with sorted arrays.
Top comments (1)
Well laid out!