Binary Search in Javascript

Written on 10/04/2021

Binary Search is an important algorithm to know if you are writing computer programs. There are many articles out there and I don't want to re write it again. Anyway, I will mention in the reference section.

You can use binary search to find if value exist in the array or not.

Time Complexity: O(log n)

Things to note:

Needed sorted array

Array must includes integer

You can use this to Find the minimum element in a sorted and rotated array.

Find square root of a large number in O(logn) time

For testing Javascript codes, I use RunJS which is really easy to use.

Iterative method

Code

function binarySearch(arr, number) {
  var start = 0;   // start index
  var end = arr.length - 1;  //end index
  while (start <= end) { 
    var mid = Math.floor((start + end) / 2); //middle index
    if (arr[mid] == number) return true; 
    else if (number < arr[mid]) {
      end = mid - 1;
    } else if(number > arr[mid]) {
      start = mid+1;
    } else {
      return false;
    }
  }
}
//Driver code
let arr = [1, 3, 4, 6, 12, 35, 40, 45, 57];
let number = 45;
binarySearch(arr, number);

Recursive Method

// Incomplete ...Coming Soon
function binarySearchRecur(arr, number) {
  var start = 0;   // start index
  var end = arr.length - 1;  //end index
  
}
//Driver code
let arr = [1, 3, 4, 6, 12, 35, 40, 45, 57];
let number = 45;
binarySearch(arr, number);

References:

Where is binary search used in practice?

Semiconductor test programs used for measuring digital timing or analog levels make extensive use of binary search. Automatic Test Equipment (ATE) from Advantest, Teradyne, Verigy and the like can be thought of as truth table blasters, applying input logic and verifying output states of a digital part.

https://stackoverflow.com/questions/540165/where-is-binary-search-used-in-practice

Binary Search - GeeksforGeeks

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[]. A simple approach is to do linear search.The time complexity of above algorithm is O(n). Another approach to perform the same task is using Binary Search.

https://www.geeksforgeeks.org/binary-search/

JavaScript Algorithms: What Is Binary Search, A Detailed Step-By-Step, And Example Code

Binary Search ONLY works with Sorted Arrays. In Computer Science, Binary Search (Half-Interval Search) is a Search Algorithm to find a specific element located in an Array ( ONLY works with Sorted Arrays). Binary Search is advantageous over a standard Linear Search because it searches faster and more efficiently due to what some developers call as " Dividing and Conquering."

https://medium.com/@jeffrey.allen.lewis/javascript-algorithms-explained-binary-search-25064b896470