I am waiting for this moment for a long time and I am glad that eventually, I can write this post. I started to learn Algorithms some time ago, but until now I decided to put my knowledge here not in Python as I’ve done many times on this blog, but in Javascript, because currently it is the main language which I use and I think it can be helpful to get to know some algorithms and data structures in this language.

So, let’s begin.

What is an Algorithm?

An algorithm is a set of well-defined instructions to solve a particular problem.

We can think about it as a recipe. For example, we have some ingredients (as our input): banana and water, and then we can create our recipe: Pour water into a bowl, add banana, and mix everything. Dry 12 hours. And put with fruits and nuts. Enjoy. As you see we have here a vegan recipe for pancakes which are by the way very tasty, but anyway we have here 3 main points: ingredients, recipe, and tasty meal.

And in programming is very the same. We have input as two numbers: a, b and recipe as an algorithm: Firstly, add numbers using the “+” operator and return a value as an output. Does it mean that almost every line of code can be an algorithm? Not exactly. To be honest, we need three characteristics to say that this can be an algorithm:

1. well-defined inputs and outputs
2. each step should be clear and unambiguous
3. language-independent means you can create your algorithm in any language (we create today our algorithm in JS)

OK, hold a second but why do we need those algorithms, we all can write the code alone with no help. Yes, we can but many times we come across problems which are very similar and somebody found that solution and share it with us and did this very efficiently that is why it will be helpful to “know some of these recipes for our delicious code”.

Let’s start with the very basic algorithm.

Linear Search vs Binary Search In Javascript

First of all, we should define our problem:

Given an array of n elements and a target element t. Find the index of t in the array. Return -1 if the target element is not found.

We can start with example arr = [ -5, 2, 4, 10, 5], and we want to find for example t = 10. We can go over every element in the list and check if it is present in the array by checking the index. If we finish checking and won’t find any such an element we return -1.

function linearSearch( arr, t){
      for(let i = 0; i <= arr.length; i++){
          if(arr[i] === t){
              return i
          }
      }
      return -1
}

It seems everything is fine if we have very few elements, but if we want to check every element it takes n times, in Big O notation we say: O(n) and it is not as quick as we want, we can then go to another algorithm: Binary search which eliminates a number of elements by half and it is much quicker than our linear search. However, elements on the array need to be sorted.

function binarySearch (arr, t){
    let leftindex = 0
    let rightindex = arr.lenght -1
    while( leftindex <= rightindex){
        let middleindex = Math.floor(( leftindex + rightindex)/2)
        if(target === arr[middleindex]){
            return middleindex
        }
        if(target < arr[middleindex]){
            rightindex = middleindex -1
        }else{
            leftindex = middleindex + 1
        }
    }
     return -1
}

So how long does it take? In notation Big O: it takes O(logn). You can take of course pencil and paper and check it out. If you have any questions or find any bugs or typos, please let me know below.

Happy Coding!