Simplified binary and linear search algorithm with JavaScript.

In a loose term, algorithm is simply sequence of steps in solving a particular problem or arriving at a solution to a problem. Since software development is geared towards problem solving, algorithm has always been a core of computer science and programming.

In recent times, developers have argued the relevance of algorithm in software development interviews, it remains a mainstream of questions asked by big tech companies.

Though one might hardly use those named algorithms in place of work, it helps you understand core principles of software development, pattern of problem solving and mastery of programming concepts. Mastery of algorithm involves learning of patterns to different problems.

I will be highlighting the key steps that should come to your mind when solving linear and binary search problems with pseudo code.

NB This approach is transferable to any programming language.

Linear Search

This is a process of iterating over an array to search for a given element. For example, one can check if a given number exists in an array. It sequentially checks each element of the list until a match is found or the whole list has been searched. Lets get our hands dirty with some codes.

Given an array of integers say [1,2,4,6,8,9,14, 19] . Write an algorithm to check if a given number exist in the array.

Our first approach to any coding problem is to write out our pseudo code.

1. Create a function that accepts two arguments.
2. Loop over the array.
3. Check if the current element is equal to the item you are searching for.
4. Return 1 if found.
5. Return -1 if not found.

function linearSearch (arr, value) {
 for(let i = 0; i < arr.length; i++) {
  if(arr[i] === value) return 1; 
 }
 return -1;
}
linearSearch([1,2,4,6,8,9,14, 19] , 9) // returns 1

Binary Search

This approach involves searching a sorted array by dividing it into two halves. It makes a guess where the searched item might be(either right halve or left halve) contained in the array and discards the other halve. The trends continues until it makes the correct guess. This is known as divide and counter pattern. Using the previous example lets implement binary search.

Pseudo code

1. Write a function that accepts two arguments.
2. Create a start index, end index and middle index of the array.
3. Write a while loop.
4. If the element of middle index is equal to what we are searching for return the index.
5. If the what we are looking for is less than the element of the middle index , move the right pointer to middle and vice versa.
6. If the item is not found return -1.

function binarySerach(arr, value) {
 let start = 0;
 let end = arr.length -1;
 let middle = Math.floor((start + end)/2);
 while (value !== arr[middle] && start <= end) {
  If (value < arr[middle]) {
   end = middle -1;
  }else {
   start = middle + 1;
  }
   middle = Math.floor((start + end)/2)
 }
 return value === arr[middle] ? middle : -1;
}
binarySearch([1,2,4,6,8,9,14, 19] , 9)

If you are yet to understanding the above implementation, try running the code in debugging mode.

About The Author

Nwafor Jude is a software developer @sterling bank. You can follow me on twitter @thaddydore