Binary Search - The most popular search algorithm

The name of this algorithm indicates clearly that we are trying to search for an element from the array. As the linear search would increase time complexity to O(n), we shall go with Binary Search. Searching an element from the array would need that to be sorted first. If you want to know how you can sort an array using Selection Sort, please refer to my other post here.

Let us first understand how the Binary Search works. The idea of this algorithm is to find the average of minimum and maximum indexes from the subset of the array, running this in a loop until we find the search element. To understand this better, say we are looking for the word "Rainbow" in a dictionary. As the pages in the dictionary are already sorted, we can use the Binary search for this problem. Instead of going page by page to find the word, we could open a random page from the middle. Here, say we found words that start with the letter S, 'Sarah', 'Sun', etc. Now we move forward and open a page that comes after the letter S and before the letter Z. In this first iteration, we eliminate the pages that come before the letter S. We can continue to iterate this until we find the desired word. Similarly, we keep shifting the minimum index and maximum index to the average by checking if the average index is equal to the target value's index.

We can achieve this in two ways - by iteration and by recursion. Let us first check how can we achieve this by iteration:

var binarySearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var assumedIndexOfTargetValue;
    while ( max >= min){
        assumedIndexOfTargetValue = floor(( min + max ) / 2);
        if(array[assumedIndexOfTargetValue] === targetValue){
            return assumedIndexOfTargetValue;
        }
        else if( array[assumedIndexOfTargetValue] < targetValue ){
            min = assumedIndexOfTargetValue + 1;
        }
        else {
            max = assumedIndexOfTargetValue - 1;
        }
    }
    return -1; //if we don't find the targetValue
};

var evenNumbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38];

var result = binarySearch(evenNumbers, 34);
println("Found 34 at index " + result);

Let me break the above program into simple steps:

  1. Setting minimum value to the initial index and maximum value to the length of the array.
  2. Once the maximum index is less than the minimum index, that means we have covered all the elements and we have not found the element.
  3. Setting the average of the minimum index and maximum index to a variable - assumedIndexOfTargetValue
  4. Now we have three conditions to check. Firstly, if the array value at assumedIndexOfTargetValue is equal to the search value, then we found the position of the search value.
  5. If not, then we check if the array value at assumedIndexOfTargetValue is less than the search value, then we change the value of the minimum index to assumedIndexOfTargetValue plus 1.
  6. Finally, the last condition is to check if the array value at assumedIndexOfTargetValue is greater than the search value, then we change the value of the maximum index to assumedIndexOfTargetValue minus 1.

We can achieve the same by using recursion as well. Instead of running it in a loop, we could call the same function to achieve Binary Search. Let us check the code snippet below on the same.

var binarySearchUsingRecursion = function(array, targetValue, min, max) {
    if ( max >= min){
       return -1;
    }
    var assumedIndexOfTargetValue = floor(( min + max ) / 2);

    if(array[assumedIndexOfTargetValue] === targetValue){
            return assumedIndexOfTargetValue;
    }
    else if( array[assumedIndexOfTargetValue] < targetValue ){
            binarySearchUsingRecursion(array, targetValue, assumedIndexOfTargetValue + 1, max);
    }
    else {
          binarySearchUsingRecursion(array, targetValue, min, assumedIndexOfTargetValue - 1);
    }
};

var evenNumbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38];

var result = binarySearchUsingRecursion(evenNumbers, 34);
println("Found 34 at index " + result);

That's all for now. I hope this was helpful. Thanks for reading so far. Happy Learning!