Linear and Binary Search in JavaScript

We live in real practical world. Here some people are godly and some are like monster. So, we are searching though the database of world for godly people. We don’t know it is there in list or not but we gotta search. If it is there we have to locate. So firstly we implement the easy way i.e; Linear search.

It easy approach because we just have to loop through an array of elements and return match. Hurrray💃😎!!

Easy, peasy, lemon squeezee….Here we’ll return the position of first godly one in array i.e; 0.

here after removing the break and adding one more godly people in our array we’ll get the last position of godly one in array i.e; 6.

But they say we shouldn’t get shortcut🤪. Here they are true. Linear search comes with a tradeoff. Here we have to loop through an array to find the specific element. So, it’s performance depends on the data size (size of array). If array is small we can use linear search but if size of array is large (in our case😀 i.e; array of types of people across the world) it’s not a good idea to implement linear search at all as it scans one item at a time, without jumping to any item. So if there are 4 elements in array linear search will traverse through those 4 elements, if there are n elements in array linear search will traverse though all those n elements. So it’s complexity is 0(n). It’ll take time as per number of elements in array.

But they also said every problem comes with a solution. Gyaani!!😜

So here is our solution :- Binary Search. Yess!! it is there. Binary search resolves the problem that linear search created i.e; complexity of 0(n).

Binary search cuts down the search complexity to half as soon as you find middle of a sorted list. Which means it’ll take half of the time that linear search took. If linear search took n it’ll take n/2 or we can say log(n).

Here we’ll see how.

ohh! code looks more lengthy than linear search. But as they say nothing worth having comes easy😀. gyaan overflowing😀😀.

Here what we are doing is we are dividing the array in two parts. So if length of array is n. We are dividing the array in two parts of size n/2. And we’ll compare only one part based on middle elements. Inside the while loop we are getting the index of middle element and we are comparing the middle element with our target. If we find that value at middle position itself we will return that position. So here the complexity of algorithm will be 0(1). We didn’t have to traverse the array at all and we found the target value at middle position.

else we’ll check if middle element of array is greater than target than we’ll decrease the the index of right element and we’ll again traverse though array again.

If middle element is lesser than middle element then we’ll increase the count of left element and will traverse the array accordingly.

In any of the above two cases, we are only traversing half of array so here the complexity of search algorithm. is 0(log n).

You know?😀 They said nothing’s perfect.😀 Oh my god!! you must be irritated by now😀. Binary search also comes with a trade off. In binary search array must be sorted.

So, chose your searching algorithm wisely. If array size is large and sorted, obviously we should use binary search because it’s complexity is 0(log n) otherwise if array size is small or not sorted use linear search. In that case, complexity of algorithm will be 0(n).