Introduction

Two of the most fundamental set of algorithms in computer science are: Sorting and Searching.

Search algorithms are step-by-step instructions to locate some specific data in a collection.

Types of Search Algorithms

Two important search algorithms are:

1. Linear Search
2. Binary Search

In the next paragraphs, we will introduce these two algorithms with examples, a code implementation in JavaScript, find the time complexity and finally, try and solve exercises.

Example

Suppose you are searching for the word "summer" in the dictionary. You could start from the first page of the dictionary and keep flipping pages until you reach the "S" es and find your word there.

But flipping every page of the dictionary doesn't make sense, right? Intuitively you know that the words starting with S will probably be after the middle of the dictionary.

This is a search problem, and these two variations of how you can search are the linear and binary search algorithms.

Linear search

In a linear search algorithm, we don't care if the array is sorted or not. The linear algorithm takes as arguments a sorted array and an item.

The algorithm will traverse the whole collection. For each element, we ask the question: "Is this my target value?". If the item is in the array, the function returns its position. If the collection traversal finishes and we have not find the target element, we return null.

const linearSearch = (arr, target) => {
   for (let i = 0; i < arr.length; i++) {
       if (arr[i] === target) {
           return i;
       }
   }

   return null;
}

linearSearch([2,5,4,3], 4); // returns the index = 2;

Binary Search

The binary search algorithm works on a sorted collection of elements (as a dictionary - which is sorted alphabetically). If the binary search finds the item in the collection it returns true (or the position where we find it). Otherwise, we return a falsy value as null or false.

The binary search algorithm takes as arguments a sorted array and an item. If the item is in the array, the function will return its position.

Each time we check the middle element, this is our guess. If the guess it is too low we update the low index.

If the guess is too high, we update the high.

const binarySearch = (arr, item) => {
    let low = 0;
    let high = arr.length - 1;

    while(low <= high) {
       const mid = Math.floor((low + high) / 2);
       if (arr[mid] === item) {
          return mid;
       } else if (arr[mid] < item) {
          low = mid + 1;
       } else {
          high = mid - 1;
       }
    }
    return null;
}

binarySearch([1,2,3,4,5], 3); // returns the index: 2

The low and high variables keep track of the part of the array we are searching. The loop will run until we have one element in the collection. For each item, we check the middle element and see if it is our targeted item. If our guess is too high, we discard the second half of the array. Otherwise, we discard the first half of the array.

Time complexity

To explain the time complexity, let's see an example.

Imagine we have an array of numbers between 1 and 100. The target is to guess which number i am thinking (e.g. a random number).

With a linear search algorithm, you will start guessing: - "Is it 1?" - "Is it 2?". At some point you will find the number. If the random number was 100, it would take 100 guesses to get there. If the colleciton was consisting 4 billion numbers, it would take up to 4 billion guesses. So the maximum number of guesses is the same as the size of the collection.

That means that the linear search algorithm, is growing in linear time. We call this linear complexity and it is written it as O(n).

For the binary search, you will start guessing with the middle element first: "Is it 50?" If this is too low, you know that all the numbers in 1 to 50 are also too low. In each guess, you eliminate half of the array.

If we have 100 numbers, we eliminate to 50, to 25, to 13, to 7, to 4, 2 and 1. So you can find every number between this range with maximum 7 guesses. If the list was consisting 4 billion numbers, it takes at most 32 guesses. We call this logarithmic complexity and we write it as O(logn)

Exercise 1

Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

This problem asks us to write an algorithm of O(logn). Additionally it mentions that our array is sorted. This should make us think the binary search.

Pseudocode:

1. We do the binary search algorith, if the element is found we return the position
2. If the element is not found, the low and high variables will point to the closer value

const searchInsert = (nums, item) => {    
    let start = 0;
    let end = nums.length - 1;

    while(start < end){
        let mid = Math.floor((start+end)/2);
        if (nums[mid] === item) return mid;
        nums[mid] > item ? end = mid : start = mid + 1;
    }

    if (start === end){
        return item <= nums[start] ? start : start + 1;
    }
};

searchInsert([1,3,5,6], 5) // returns 2
searchInsert([1,3,5,6], 2) // returns 1, as if the 2 existed would be between 1 and 3

Exercise 2

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

For this problem, the array is sorted, so we find the first negative index. So all remaining items are negative.

const countNegatives = function(grid) {
    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        const index = binarySearch(grid[i]);
        count+= grid[i].length - index;
    }

    return count
};

const binarySearch = (arr) => {
    let low = 0;
    let high = arr.length - 1;
    while(low <= high){
        const mid = Math.floor((low+high)/2);
        if(arr[mid] < 0){
            high = mid-1;
        }else{
            low = mid+1;
        }
    }
    return low;
}