Last Updated on
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:
- Create a variable
min , set it to 0 - Create a variable max, set it to array length – 1
- Create a variable guess
- While min is less than or equal max, keep going
- Add min and max and divided them by 2; make it an integer
- if the target value equals the value in the index of guess, return the guessed index
- If the guess is higher than the target value, set max to guess – 1
- If the guess is less than the target value, set min to guess + 1
- Go to step 4
- Return -1 if the target value is not in the list
Simplified version:
Looking for a Node.JS course recommendation? Check out The complete Node Developer course by Rob Percival - see others
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; }