Binary Search Algorithm | Javascript

The binary search algorithm works on the principle of divide and conquer. Before searching, the array has to be in the sorted form then the middle element in the array is checked. If the match is found the element index is returned.

If the middle element is less than the searching element then the search happens in the right sub-array otherwise, the search happens in left sub-array

Let's write some code

Consider an array of numbers, remember array indexing starts form zero '0'.

const numbers = [4, 10, 12, 26, 34, 39, 42, 57];

Now we have a function with arguments as sorted array and the number which we need to find.

function binarySearch(sortedArray, x) {
  let lowIndex = 0;
  let highIndex = sortedArray.length - 1;

  while (lowIndex <= highIndex) {
    let midIndex = lowIndex + Math.floor((highIndex - lowIndex) / 2);
    if (sortedArray[midIndex] === x) {
      return midIndex;
    } else if (sortedArray[midIndex] < x) {
      lowIndex = midIndex + 1;
    } else {
      highIndex = midIndex - 1;
    }
  }
  return -1;
}

binarySearch(numbers, 10); // returns 1
binarySearch(numbers, 34); // returns 4
binarySearch(numbers, 63); // since 63 is not there in numbers, returns -1

// Save the file and run it using Node.JS
// Open terminal and give command: node [filename].js

Math.floor() function rounds a number downward to its nearest integer.
for example: Math.floor(2.5) // returns 2

Time Complexity

The time complexity of Binary Search Algorithm is O(log n).

• Best case scenario O(1), if the finding element is at centre.
• Worst case scenario could be when the finding element is present at extremely left or right from centre and if it is not at all present in array.

Well, that's it folks. I hope you learned something share it with your friends. Follow me for more posts just like this and
if you have any questions let me know in the comment section.

Cheers!