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:
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