Search Algorithm’s Part 1

Search algorithm’s are an awesome way to return data from a large collection. Search algorithms are used to check for an element in any data structure that is it stored. Although some processes are more time consuming than others, they are under the same roof of searching algorithms. Today we are only going to focus on two types of search algorithm’s.

Liner Search- Liner search is a simple algorithm that checks each item to see if it matches a particular item and returns it or returns a given a value if . Because liner search operates on each item, this can work for a sorted or unsorted array. This search is helpful for working with smaller data sets. The best case time complexity for a liner search is O(1) and the worst case is O(n). Below is an example of what the pseudocode would look like

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure

Binary Search- Binary search is a slightly more complicated algorithm that compares a value to the middle element of a sorted array. If the value is not equal to the middle, the array is divided in half, and depending on if the value is greater than or less than the middle value, a new middle is assigned. Below is a diagram of how it works.

Heres what the pseudocode of what something like this would look like in code.

function binarySearch(sortedArray, key){  
   let start = 0; 
   let end = sortedArray.length - 1; 
     while (start <= end) {  
       let middle = Math.floor((start + end) / 2);   
       if (sortedArray[middle] === key) {    
          // found the key         
         return middle;         
      }else if (sortedArray[middle] < key) { 
          // continue searching to the right       
         start = middle + 1;         
      } else {         
         // search searching to the left      
         end = middle - 1;        
      }    
    } 
 // key wasn't found     return -1;
 }

The Difference- The time complexity for Binary search is O(log n). Which is far more efficient when dealing with larger databases. The reason being is because, although there is many steps needed, it is far less time consuming than a liner search. Here we found 23 in 4 steps, however if we did a liner search it would have taken us 6 steps to return the correct index. Yes that difference seems minuscule, but when we compare it on a larger scale the difference is definitely worth considering. Below is a visual representation.

Happy Coding!