Binary Search Algorithm in JavaScript

Binary Search algorithm cuts the list in half to find the given item. Here I will be implementing binary search algorithm in JavaScript.

Pseudo code:

  1. Create a variable min, set it to 0
  2. Create a variable max, set it to array length – 1
  3. Create a variable guess
  4. While min is less than or equal max, keep going
  5. Add min and max and divided them by 2; make it an integer
  6. if the target value equals the value in the index of guess, return the guessed index
  7. If the guess is higher than the target value, set max to guess – 1
  8. If the guess is less than the target value, set min to guess + 1
  9. Go to step 4
  10. Return -1 if the target value is not in the list

Simplified version:

function binarySearch(array, item) {
  let min = 0;
  let max = array.length - 1;
  let guess;
  while (min <= max) {
    guess = Math.floor((min + max) / 2);

    if (array[guess] === item) {
    } else if (array[guess] > item) {
      max = guess - 1;
    } else {
      min = guess + 1;
    }
  }

  return -1;
}

And here’s a heavily commented version which logs number of guesses it took

function binarySearch(array, item) {
  let min = 0;
  let max = array.length - 1;
  let guess;
  let numberOfGuesses = 0;
  // While the min number is less than or equal to max number, keep looking.
  while (min <= max) {
    // Make a guess at half point, and make it an integer
    guess = Math.floor((min + max) / 2);
    numberOfGuesses++;
    // See if the guess is right!!
    if (array[guess] === item) {
      console.log('Total number of guesses', numberOfGuesses);
      return guess;
      // But if the guess is greater than the number
      // Reset the maximum
    } else if (array[guess] > item) {
      max = guess - 1;
    } else {
      // The guess must be lower than the number
      min = guess + 1;
    }
  }
  console.log('The number was not in the list.');
  return -1;
}

Leave a Reply

Your email address will not be published. Required fields are marked *