Linear and Binary Search in Javascript

When preparing for technical interviews there are a ton a material to cover and prepare for. The most important thing is coming up with a solution that works and then later showing that you can refactor and optimize your solution. To help in coding problems that require you to search through a set of data there are two very easy ways to do this. Of course there are more advanced ways but these searching techniques are easy to remember and get the job done. You can always go back to refactor and optimize later.

Linear Search

This is the most basic form of searching. Its pretty simple, you just iterate through your data set one at a time till you find what you are looking for. This can be done with a simple loop. Linear search works on both sorted and unsorted data. Since we are going through are data point by point, that means in the worst case we will have to go through every element. If we have a very large dataset, this could take a long time. Here is an example of what a linear search looks like:

function linearSearch(array, number){
   for(num of array){
      if(num === number){
         return true
      }
   }
   return false
}

What the code is doing is very simple. All we are doing is looking at each element of the given array and comparing it to the number passed in. Once it finds a match it will return true or if there is no match it will return false. This can be used on sorted or unsorted data but usually just on unsorted data. There are better solutions for sorted data like Binary search.

Binary Search

Binary Search is a way we can dramatically speed up our searching in large data sets. There is one important thing that you have to keep in mind with this technique. The data set has to be sorted for it to work. If you do this with an unsorted data set it will NOT work. The whole objective of Binary search is to reduce the size of the data we are looking through. We will divide our code and check to see if the value we are searching for is in the first half or the second half. This reduces the data we are searching through in half. We can keep repeating this reduction till we have our answer or no more data to reduce.

To get a better Idea of how this works here’s a visual example:
let searchData = [1,2,3,4,5,6,7,8,9,10]
searching for = 8

=> [1,2,3,4,5] [6,7,8,9,10] //we can tell by looking that 8 is in the second array. This means we can remove the first array from consideration
=> [6,7,8] [9,10] //We reduce again and can see that 8 is in the first array this time
=> [6,7] [8] // 8 is in the second array
=> [8] //this is equal to the value we are searching for and we are now done!

If we did this same search in a linear fashion it would have took us 8 passes to get to our answer. With binary search we did the same task but with only 4 passes. Thats major! Imagine the difference if we had an array with thousands of elements.

To do this in code there are a couple of steps you need to remember to get it to work. We need to start the function by creating 3 variables. The left point will represent the start of the array and the beginning of our sectioned array. The right point will be the end of our sectioned array. Lastly, the midpoint will be the point in our array where we compare our value to see what half our value will be in. Once we create these variables it is time to start searching. We do this with a while loop. We are going to do our divide and conquering till we either find our solution or our left variable is greater than our right variable.

In our while loop depending on if our search value is bigger or smaller than our midpoint will determine what variable we reassign. If our search value is greater than our midpoint then we know everything to the left of our midpoint is to small. We then move our left point to what our midpoint is. We can actually move it one spot past our midpoint because we know that our midpoint is not equal to our value. Once we do that, we reduced the size of the array we are looking at. We recalculate our midpoint inside of this reduce section and repeat the process. Here is what it looks like in code:

function binarySearch(array, number){

   let leftPoint = 0
   let rightPoint = array.length - 1
   let midPoint = Math.floor((leftPoint + rightPoint)/2)

   while(array[midPoint] !== number && leftPoint <=  rightPoint){
      if(number < array[midPoint]) {
         rightPoint = midPoint -1
      } else {
         leftPoint = midPoint + 1
      }
   midPoint = Math.floor((leftPoint + rightPoint) / 2)
   }

   if(array[midPoint] === number){
      return true
   }
   return false;
}

The whole premise of Binary search is to keep reducing your data set till you find your solution. This greatly reduces the time it takes to find a value in a large data set. Remember this only works for sorted data. If you have unsorted data you, will need to either sort it or use a technique like the Linear search or something similar.

To wrap everything up, searching is a very important part of programming. There are two elementary ways of searching that are easy to implement when under pressure during a coding interview. The Linear search is the most stream line and works with unsorted data. The Binary search is much quicker but only works on sorted data.