Searching in JavaScript…
Hi guys , in this blog we will be discussing in details different searching algorithms , what are their time complexity, pros and cons and logic . So let’s get started …
Searching :
Searching , the most deepest word in this world , people spend their entire life searching for peace , love and what not , but wait wait wait !! let’s not get into those deep philosophical norms :) ….. For us as a geek let see how do we search ?
In an array the simplest way to search for an value is to look at every element in the array and check if it’s the value we want .
The biggest example of significance of search is Google, it’s nothing but a search engine , and I think you all will agree with me that google is having the world most complexed searching algorithms. So we will explore how we can do searching using Javascript .
Javascript is also having it’s own search function , there are many different search methods on arrays like :
1> indexOf : The indexOf() method of Array instances returns the first index at which a given element can be found in the array, or -1 if it is not present.
2> includes: The includes() method of Array instances determines whether an array includes a certain value among its entries, returning true or false as appropriate.
3> find : The find() method of Array instances returns the first element in the provided array that satisfies the provided testing function. If no values satisfy the testing function, undefined is returned.
4>findIndex: The findIndex() method of Array instances returns the index of the first element in an array that satisfies the provided testing function. If no elements satisfy the testing function, -1 is returned.
But how do these functions work ?
And the answer is our very first and simple searching algorithm :
Linear search :
Linear search is nothing but normal search algorithm where we will check every element in an array , and compare whether it’s the value we are looking for . Let’s see one example :
We are having one array [5 , 8 , 1 , 100 , 12 , 3 , 12 ] so let’s search for 12 . We will start checking from the first element , first element is 5 , not 12 , so we will check second , it’s 8, not 12 , we will check third , it’s 1 , not 12 , then we will move on the 4th , it’s 100 , not 12 , then on 5th , now it’s 12! . Simple right . So before jumping into the coding part let see the pseudocode for Linear search :
We will have one function which accepts an array and a value. We will loop through the array and check if the current array element is equal to the value , if it is we will return the index at which the element is found , else if the value is never found we will return -1.
Now let see the code :
function linearSearch(arr, val){
for(var i = 0; i < arr.length; i++){
if(arr[i] === val) return i;
}
return -1;
}
linearSearch([34,51,1,2,3,45,56,100], 100)Code Walkthrough:
So here we have defined a function linearSearch which are having two parameters arr and val , arr is the array in which we will be searching the element, and val is the element to be search , then we are iterating through the array using for loop and checking if arr[i] == val, means if there are any array element which is matching with val , if we encounter such element we will return i means the index of a element , else if the whole array is iterated but the element is not found we will return -1 means array is not having the element.
Now let see the time complexity of linear search: In this algorithm the best case scenario will be if the element we are searching is in the first index , O(1) ,and and worst case scenario will be if the element which we are searching is in the last index , O(n) . So the time complexity will be O(n).
Now we will see a much faster form of search which is :
Binary Search:
Binary search is a much faster form of search , Binary search only works on the sorted arrays! so rather than eliminating one element at a time like linear search , we can eliminate half of the remaining elements at a time . Let’s discuss in details, so binary search follows Divide and Conquer approach , let say we are having a sorted array [1,3,4,6,8,9,11,12,15,16,17,18,19] and let search for 15 , so first we will determine the element which is in the middle of the array , since the array is having 13 element so 7th element will be the mid element of the array which is 11 , we will check whether the mid element is greater or less than the element we want to search . Since 11< 15 we will be ignoring the left side of the array , and will only search on the right side of the mid element , now the array will be [12,15,16,17,18,19] so now mid element will be 17 , since 15<17 , we will ignore the right side of the mid element , so now the array will be [12,15,16] , now 15 will be the mid element and it’s the same element we are searching for ! So this is how binary search works. Now let’s see the pseudocode of Binary search:
We will be having a function that accepts a sorted array and a value . We will create a left pointer at the start of the array , and a right pointer at the end of the array . While the left pointer comes before the right pointer , we will create another pointer in the middle , if you find the value you want , return the index , if the value is too small , move the left pointer up , if the value is too large , move the right pointer down , and lastly if you never find the value return -1.
Now let’s see the code :
// Original Solution
function binarySearch(arr, elem) {
var start = 0;
var end = arr.length - 1;
var middle = Math.floor((start + end) / 2);
while(arr[middle] !== elem && start <= end) {
if(elem < arr[middle]){
end = middle - 1;
} else {
start = middle + 1;
}
middle = Math.floor((start + end) / 2);
}
if(arr[middle] === elem){
return middle;
}
return -1;
}
// Refactored Version
function binarySearch(arr, elem) {
var start = 0;
var end = arr.length - 1;
var middle = Math.floor((start + end) / 2);
while(arr[middle] !== elem && start <= end) {
if(elem < arr[middle]) end = middle - 1;
else start = middle + 1;
middle = Math.floor((start + end) / 2);
}
return arr[middle] === elem ? middle : -1;
}
binarySearch([2,5,6,9,13,15,28,23], 103)Code Walkthrough:
We are having binarySearch function which is having two parameters arr and elem , arr is the array is which we will be searching , elem is the element we will be searching . So we have declared two pointer start pointing to the first element and end pointing to the last element of the array. Then we are declaring the middle pointer of the array middle which points to the middle of the array . Now we are will writing the actual logic , we have defined a while loop , while middle element is not equal to search element and start pointer is less than or equal to end pointer means array iteration is not completed , we are checking if the search element is less than middle element we will set end pointer to previous element of middle element , else we will set start pointer to next element of the middle element , and again we will define the middle pointer according to the start and end pointer defined . Then if the while condition gets failed we will check whether the element which is getting pointer by middle pointer is equal to search element, if it is true it means element is found so we will reach the index of the element . if it is false it means the element is not there in the array and we will return -1.
Now let’s see the time complexity of the Binary Search , in the best case scenario , the time complexity will be O(1) and worst and average case the time complexity will be O(log n) . Let justify the statement , so we will see two example , let’s say we are having an array [2,4,5,9,11,14,15,19,21,25,28,30,50,52,60,63] and we are searching 13, so the iteration will be [2,4,5,9,11,14,15] →[11,14,15] →[11], the array is having 16 elements and we are having 4 iteration , so log 16 is 4 . Now let’s see the next example , now we are having an array [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,32,35] so total 32 elements in array , and we will search 32 , so the iteration will be [17,18,19,20,21,22,23,24,25,26,27,28,29,30,32,35] →[25,26,27,28,29,30,32,35] →[29,30,32,35] →[32,35] →[35] , finally we are able to find the element with 5 iteration, so log 32 is 5. So we can say the time complexity of binary search is O(log N).
Now let’s see own last concept of search algorithm which is Naive String search
Naive String Search:
Suppose we want to count the number of times a smaller string appears in a longer string . So a straightforward approach involves checking pairs of characters individually . Let’s try to understand this through an example, so we are having a long string wowomgzomg and short string omg , we will start comparing the large string with short string , w of large string is not matching with o of short string , so we will move on for large string , now o of large string is matching with o of short string , so we will check the next character for both the string , but since w of large string is not matching with m of short string , for short string the iteration will again start from o , now again w of large string is not matching with o of short string , so only the pointer of larger string with move , now since the three consecutive text omg for large string is matching with omg of short string , we will increment the count by 1 , and same process will be followed and once large string is iterated completely , the count value will be returned .
Now let’s see the pseudocode :
We have to loop over to longer string , then we have to loop over to shorter string , if the character don’t match , break out of the inner loop , if the character do match , keep going . If you complete the inner loop and find a match , increment the count of matches , return the count .
Now let’s see the code :
function naiveSearch(long, short){
var count = 0;
for(var i = 0; i < long.length; i++){
for(var j = 0; j < short.length; j++){
if(short[j] !== long[i+j]) break;
if(j === short.length - 1) count++;
}
}
return count;
}
naiveSearch("lorie loled", "lol")Code Walkthrough:
So we are having naiveSearch function which is having two parameters long and short string . Now we have defined a variable called count which used to store the count of occurrence of short string inside the large string . Now we are running a loop over long string and short string , and then we are checking if (short[j]!==long[i+j]) means if the characters of short string don’t match with large string , we will break out of the inner loop. and if the character matches we will keep going and if (j==short.length-1) means if we complete the inner loop and find a match, increment the count of matches, and finally will return match count .
Now what will be the time complexity of Naive String Search , so let assume the length of element in large string is n and that of short string is m , so since we are iterating through both the string the time complexity of naive string search will O(n*m).
Conclusion:
Okay so we did it ! , we have touched almost all the corners of search algorithm in JavaScript . But please don’t stop searching :) . Do checkout my github repo for the reference of the code snippets discussed in this blog …
HAPPY CODING :)
