This is my second article on data structures and algorithms series. In this article, you will learn about linear and binary search algorithms, their implementation in javascript and their time complexities. You will also learn about different sorting techniques like selection sort, bubble sort, insertion sort, quick sort, and merge sort which are some of the most important topics during interviews.

Search Algorithms

If you have an array and you want to search for an element in it, there are 2 ways to do this. These 2 ways are called search algorithms and they are as follows:

Linear Search

Suppose you have an array arr = [5,2,7,3,6]. You want to search for an element e =7 in that array. To do this, the algorithm will be:

• Loop from the first element to the last element of the given array

• At every loop iteration, check if the element e matches the value at arr[i] where i is the current iterated index of the loop. If this is so, return the found element's index i

• Else, at the end return -1

This is how the code for the linear search algorithm in javascript looks like:

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

console.log(linearSearch([5,2,4,6,2],4))
// Output: 2

console.log(linearSearch([5,2,4,6,2],27))
// Output: -1

Time Complexity: O(n) since our function will iterate all elements in array of size n

Binary Search

Most of the time you will only use linear search algorithm. However, suppose you have an array in which the elements are sorted in ascending order. To search for an element in this kind of array, instead of using linear search algorithm, you can use binary search algorithm which will improve the efficiency of the algorithm by reducing the time complexity.

So, suppose you have a sorted array arr = [10,14,26,32,68]. You want to search for an element e =32 in that array. To do this, the algorithm will be:

• First, check if the array is empty or not. If the array is empty, return -1

• If the array is not empty, find the middle element. If the middle element matches the element to be searched e, return its index

• If e is less than the middle element, get the middle element of the array from 0 to the current middle element and perform binary search there. Else, if e is more than the middle element, perform binary search on the array which starts from the middle element till the array's last element

This can be implemented using a while loop and using a recursive function. The code to do this is using a while loop is as follows:

function binarySearch(arr,e) {
    if(arr.length<1) {
        return -1;
    }
    let startEltIndex = 0;
    let endEltIndex = arr.length-1
    while(startEltIndex <= endEltIndex) {  
    let midEltIndex = Math.floor((startEltIndex + endEltIndex)/2)   
        if(e === arr[midEltIndex]) {
            return midEltIndex;
        }
        if(e<midEltIndex) {
         startEltIndex = 0;    
         endEltIndex = midEltIndex - 1;   
        } else {
         startEltIndex = midEltIndex + 1;    
         endEltIndex = arr.length-1; 
        }
    }
    return -1;
}

console.log(binarySearch([10,14,26,32,68],32))
// Output: 3

The code to do this is using a recursive function is as follows:

function recursiveBinarySearch(arr,e) {
    return binarySearch(arr,e,0,arr.length-1)
}

function binarySearch(arr,e,startEltIndex,endEltIndex) {
    if(startEltIndex>endEltIndex) {
        return;
    }
    let midEltIndex = Math.floor((startEltIndex + endEltIndex)/2)   
        if(e === arr[midEltIndex]) {
            return midEltIndex;
        }
        if(e<midEltIndex) {
         return binarySearch(arr,e,startEltIndex,midEltIndex-1)   
        } else {
        return binarySearch(arr,e,midEltIndex+1,endEltIndex) 
        }  
}

console.log(binarySearch([10,14,26,32,68],32))
// Output: 3

Time Complexity: O(log(n)) since our function will reduce the value of middleEltIndex by half after every iteration

Sorting Algorithms

If you have an array of numbers and you want to sort it in ascending order, you can use a sorting algorithm to do so. Although there are over 15+ sorting algorithms, I'll only discuss the 5 most important sorting algorithms among all. These sorting algoriths are as follows:

Bubble Sort

Suppose you have an array arr = [6,542,112,3,423,5]. You want to sort it in ascending order using the bubble sort algorithm. The algorithm will be:

• Create a variable called swapped.

• Loop through the entire array and if an element is bigger than the element on its right side, you swap both the elements.

• And whenever you swap 2 elements, you set the value of swapped variable to true otherwise the value of swapped variable will be false.

• When you finish looping through an array, check the value of swapped variable. If it is true, you need to loop through the array again (which you can do by wrapping for loop inside a do while loop). The array will be known to be sorted when no swapping of elements takes place.

Here is how to implement the bubble sort algorithm in javascript:

function bubbleSort(arr) {
    // A swapped variable to know if any swapping of elements occurs
    let swapped;
    do {
        // Set swapped to false by default in every iteration
        swapped = false;
        for(let i=0; i<arr.length; i++) {
            // If an array element is bigger than element on its right
            if(arr[i]>arr[i+1]) {
                // Swap both elements
                let temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                // And set swapped to true
                swapped = true;
            }
        }
    // Use while loop with swapped variable to reiterate through array
    } while(swapped);
    return arr;
}

console.log(bubbleSort([6,542,112,3,423,5]))
// Output: [3,5,6,112,423,542]

Here is how the sorting takes place in each iteration:

[ 6, 542, 112, 3, 423, 5 ] (Input array)

[ 6, 112, 3, 423, 5, 542 ] (542 moved to end)

[ 6, 3, 112, 5, 423, 542 ] (423 moved to end)

[ 3, 6, 5, 112, 423, 542 ] (112 moved to end)

[ 3, 5, 6, 112, 423, 542 ] (6 moved to end)

[ 3, 5, 6, 112, 423, 542 ] (Output array)

As you can see, every element is getting moved or bubbled to the end based on their order. That's why this algorithm is called the bubble sort algorithm.

Time Complexity: O(n^2)

Selection Sort

Suppose you have an array arr = [6,542,112,3,423,5]. You want to sort it in ascending order using the selection sort algorithm. The algorithm will be:

• Loop from the first to the last element of the input array (Eg. i=0 to i<arr.length).

• Create a variable named min. It will be the smallest element in the array. Set it to the current value of i by default (Eg. let min = arr[i]).

• Now create another nested loop from j=i to j<arr.length. We are looping through the same array twice so that we can find the minimum element in array.

• If the value of currently iterated arr[j] is smaller than min, set min = arr[j].

• Finally after every iteration, swap the currently iterated element with minimum element. This will place all smaller elements at the start and hence sort the array.

Here is how to implement the bubble sort algorithm in javascript:

const selectionSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    let min = arr[i];
    let minIndex = i;
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < min) {
        min = arr[j];
        minIndex = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

console.log(selectionSort([6,542,112,3,423,5]))
// Output: [3,5,6,112,423,542]

Here is how the sorting takes place in each iteration:

Iteration 1:

[ 6, 542, 112, 3, 423, 5 ] (Array)

Minimum element: 6 (arr[i])

Minimum element changed to 3 (arr[j]<min, 3<6)

Swapping: 3 and 6

Iteration 2:

[ 3, 542, 112, 6, 423, 5 ] (Array)

Minimum element: 542 (arr[i])

Minimum element changed to: 112 (arr[j]<min, 112<542)

Minimum element changed to: 6 (arr[j]<min, 6<542)

Minimum element changed to: 5 (arr[j]<min, 5<542)

Swapping: 5 and 542

Iteration 3:

[ 3, 5, 112, 6, 423, 542 ] (Array)

Minimum element: 112 (arr[i])

Minimum element changed to: 6 (arr[j]<min, 6<112)

Swapping: 6 and 112

Iteration 4:

[ 3, 5, 6, 112, 423, 542 ] (Array)

Minimum element: 112 (arr[i])

Swapping: No swapping needed since all elements in left of 112 are already sorted

Iteration 5:

[ 3, 5, 6, 112, 423, 542 ] (Array)

Minimum element: 423 (arr[i])

Swapping: No swapping needed since all elements in left of 112 are already sorted

Iteration 6:

[ 3, 5, 6, 112, 423, 542 ] (Array)

Minimum element: 542 (arr[i])

Swapping: No swapping needed since all elements in left of 112 are already sorted

Sorted Array:

[ 3, 5, 6, 112, 423, 542 ]

Time Complexity: O(n^2)

Insertion Sort

Suppose you have an array arr = [6,542,112,3,423,5]. You want to sort it in ascending order using the insertion sort algorithm. The algorithm will be:

• Assume the first element of array arr[0] = 6 is already sorted and the remaining elements from arr[1] to arr[arr.length-1] are unsorted

• So start a loop from i=1 to i<arr.length. This loop will iterate through all unsorted elements which are on the right side of array when seen from the sorted element arr[0].

• Start another loop from j=i to j>=0. In the first iteration, arr[0] is assumed to be sorted but in the second iteration, arr[1] will be sorted, in the third iteration, arr[2] will be sorted, and so on. This loop will iterate through all sorted elements which are on the left side of array.

• If the current iterated element (unsorted) is less than the element on its left (sorted), we swap both of them. Once the loop ends, we will get a sorted array!

Here is how to implement the insertion sort algorithm in javascript:

function insertionSort(arr) {
    // Since arr[0] is assumed to be sorted, start loop from 1
    for(let i=1; i<arr.length; i++) {
        // Loop through sorted elts which are between arr[0] to arr[i]
        for(let j=i; j>=0; j--) {
            // If unsorted elt is less than sorted elt, swap them
            if(arr[j]<arr[j-1]) {
                let temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
    return arr;
}

console.log(insertionSort([ 6, 542, 112, 3, 423, 5 ]))
// Output: [ 3, 5, 6, 112, 423, 542 ]

Here is how the sorting takes place in each iteration:

[ 6, 542, 112, 3, 423, 5 ] (Input array)

[ 6, 542, 112, 3, 423, 5 ] (542<6 false so no swapping)

[ 6, 112, 542, 3, 423, 5 ] (112<542 true so swap them)

[ 3, 6, 112, 542, 423, 5 ] (3<542, 3<112 and 3<6 so swap and bring it at first )

[ 3, 6, 112, 423, 542, 5 ] (423<542 true so swap, 423<112 false so no swap)

[ 3, 5, 6, 112, 423, 542 ] (Output array)

Since every element from the unsorted array at right is inserted into the sorted array at left, this technique is called insertion sort.

Time Complexity: O(n^2)

Quick Sort

Suppose you have an array arr = [6,542,112,3,423,5]. You want to sort it in ascending order using the quick sort algorithm. The algorithm will be:

• First, we need to choose the pivot element. A pivot element is an element that is compared with other elements in order to sort the array. A pivot element can be the first element of the array, the last element of the array, the median or any random element. Let's take the pivot element as the last element of the array, or pivot = arr[arr.length-1] = 5.

• Create two empty arrays named left and right.

• Now loop through the array from index 0 to the second last index eg. arr[arr.length-2].

• If any iterated element is smaller than the pivot element, move it to the left array otherwise move it to the right array.

• By doing this, we have divided array into 2 parts. The left array with elements smaller than pivot and the right array with elements more than pivot. Now we will repeat the above steps again and divide left and right arrays into further sub-arrays until we get arrays with only one element in them. This can be easily achieved using recursion.

• And then we will merge all the arrays containing one element together and get a sorted array as a result.

Here is how to implement the quick sort algorithm in javascript:

function quickSort(arr) {
    // If only one element remains in array, exit the function
    if(arr.length<2) {
        return arr;
    }
    let left = []
    let right = []
    // Take pivot as last element of array
    let pivot = arr[arr.length-1]
    // Loop from first to second last element of input array
    for(let i=0; i<arr.length-1; i++) {
       // Compare and move input array elements to respective arrays 
       if(arr[i]<pivot) {
           left.push(arr[i]);
       } else {
           right.push(arr[i]);
       }
    }
    // Recursively divide left and right array into sub arrays. The recursion will end when the above if condition of only 1 element in array becomes true. Then use javascript's ... spread operator to merge all sub arrays and the pivot element
    return [...quickSort(left),pivot,...quickSort(right)];
}

console.log(quickSort([ 6, 542, 112, 3, 4323, 5 ]))
// Output: [ 3, 5, 6, 112, 423, 542 ]

Here is how the sorting takes place in each iteration:

Function Starts:

Input array= [ 6, 542, 112, 3, 423, 5 ]

Pivot= 5

Left= [ 3 ]

Right= [ 6, 542, 112, 423 ]

Recursion Left:

Input array (Left array of the main function) = [ 3 ]

This recursion ends since only one element left

Recursion Right:

Input array (Right array of the main function) = [ 6, 542, 112, 423 ]

Pivot= 423

Left= [ 6, 112 ]

Right= [ 542 ]

Recursion Right's Left:

Input array (Left array of the main recursion 1) = [ 6, 112 ]

Pivot= 112

Left= [ 6 ]

Right= []

This recursion ends since only one element left

Recursion 2 Right:

Input array (Left array of the main recursion 1) = [ 542 ]

This recursion ends since only one element left

Broken Arrays And Pivots:

[ 3], [5], [6], [112], [423], [542 ]

Sorted Array:

[ 3, 5, 6, 112, 423, 542 ]

Time Complexity: O(n^2)

However, the average case time complexity of this algorithm is O(nlog(n)) which is much better than other sorting algorithms. That's why this sorting technique is called quick sort.

Merge Sort

Suppose you have an array arr = [6,542,112,3,423,5]. You want to sort it in ascending order using the merge sort algorithm. The algorithm will be:

• Find the middle element of the array

• Move the array elements from index 0 to the index before the middle element in one array. Call this array as leftAry.

• Move all remaining elements from the middle element towards the last element in another array and call it rightAry.

• Using recursion, divide the leftAry and rightAry into further subarrays until only one element remains in each subarray.

• Then create a new array named sortedAry and compare rightAry with leftAry. If element in leftAry is smaller than element in rightAry, move the element from leftAry into the sortedAry otherwise move the element from rightAry into the sortedAry.

Here is how to implement the merge sort algorithm in javascript:

function mergeSort(arr) {
    // End the function if only one element exists in array
    if(arr.length<2) {
        return arr;
    }
    let midElementIndex = Math.floor(arr.length/2)
    // Array from 0 to mid element index - 1
    let leftAry = arr.slice(0,midElementIndex)
    // Array from mid element index till end
    let rightAry = arr.slice(midElementIndex)
    // This will first divide leftAry and rightAry further and then combine them by comparingelements from both arrays
    return merge(mergeSort(leftAry),mergeSort(rightAry))
}

function merge(leftAry,rightAry) {
    // An empty array to store sorted elements
    let sortedAry = []
    // Compare and sort elements from leftAry and rightAry
    while(leftAry.length && rightAry.length) {
        if(leftAry[0]<rightAry[0]) {
            sortedAry.push(leftAry.shift())
        } else {
            sortedAry.push(rightAry.shift())
        }
    }
    return [...sortedAry,...leftAry,...rightAry]
}

console.log(mergeSort([ 6, 542, 112, 3, 423, 5 ]))
// Output: [ 3, 5, 6, 112, 423, 542 ]

Here is how the sorting takes place in each iteration:

Function Starts:

Input array: [ 6, 542, 112, 3, 423, 5 ]

Mid Element Value: 3 (Length/2 = 6/2 = 3 = arr[3] = 3)

Left Array [ 6, 542, 112 ]

Right Array [ 3, 423, 5 ]

Recursion Left:

Input array: [ 6, 542, 112 ]

Mid Element Value: 542

Left Array [ 6 ]

Right Array [ 542, 112 ]

Recursion Left's Left:

Input array: [ 6 ]

This recursion ends since only one element left

Recursion Left's Right:

Input array: [ 542, 112 ]

Mid Element Value: 112

Left Array [ 542 ]

Right Array [ 112 ]

Recursion Left's Right's Left:

Input array: [ 542 ]

This recursion ends since only one element left

Recursion Left's Right's Right:

Input array: [ 112 ]

This recursion ends since only one element left

Recursion Right:

Input array: [ 3, 423, 5 ]

Mid Element Value: 423

Left Array [ 3 ]

Right Array [ 423, 5 ]

Recursion Right's Left:

Input array: [ 3 ]

This recursion ends since only one element left

Recursion Right's Right:

Input array: [ 423, 5 ]

Mid Element Value: 5

Left Array [ 423 ]

Right Array [ 5 ]

Recursion Right's Right's Left:

Input array: [ 423 ]

This recursion ends since only one element left

Recursion Right's Right's Right:

Input array: [ 5 ]

This recursion ends since only one element left

Sorted Array:

[ 3, 5, 6, 112, 423, 542 ]

Time Complexity: O(nlog(n))

Time Complexity Cheatsheet

Here are the best, average and worst-case time complexities of all the algorithms which we discussed about in this article:

Thanks For Reading

If you enjoy reading this article, please give it a like and let me know your feedback in the comments :) For any questions, you can drop me a message on my Instagram or LinkedIn.