Binary Search in Javascript

Binary Search in Javascript

In this article, I am going to show you the importance of Binary Search and how to implement using Javascript. There are many articles out there talking about this algorithm, so I am not going to repeat it here.
It is also known as logarithmic search because of the time complexity O(log n) . If you don't what time complexity means, you can check out this article to know more. In short, the time complexity is a way to find the runtime of an algorithm.

In a practical scenario, suppose you have an app with users with names from A to Z, then you are going to use a binary search algorithm starting from the middle to find the user name. By using this algorithm, you could find an element with 7 guesses from 100 items length array and that's the power of binary search.

Things to note

  • Array needs to be sorted.
  • After each search, the algorithm will divide the array in half.

For writing Javascript snippets, I use RunJS which is really easy to use. If you are doing coding practices, then I would suggest writing on a paper first and then Text Editor (NOT IDE).

Checking if an element exists in a sorted array

1) In-built function

let arr = [2, 3, 5, 7, 10, 20 ,22, 25, 30, 33, 34, 37, 40, 46];
let searchVal = 10;

//To check if element is present or not
console.log(arr.includes(10))  // true

//To print search value index
console.log(arr.indexOf(10))  // 4

Check this one as it talks about Binary Search vs indexOf.

2) Binary Search

function binarySearch(arr, number) {
  let start = 0;   // start index
  let end = arr.length - 1;  //array length

 //LOOP until start index great than end index
  while (start <= end) { 
    let 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;
return false;
//Driver code
let arr = [1, 3, 4, 6, 12, 35, 40, 45, 57];
let number = 45;
binarySearch(arr, number);

As you can see from the code,

  • You will have three variable start, mid & end index.
  • Math.floor is used to remove floating values. JS Tip: you could also use ~~((start + end) / 2)

Useful animation 1_EYkSkQaoduFBhpCVx7nyEA.gif

Next Step

Find the square root of a large number in O(logn) time. For example, find square root of 121. Hint: Use binary search.

If you need to add anything or found anything to update please use the comment below.

Useful Readings

Join our Mailing List

Did you find this article valuable?

Support Dorothi Viki by becoming a sponsor. Any amount is appreciated!