Binary Search in 3 minutes.

“Wonder is the beginning of wisdom.” ~ Socrates

You’re looking at a book-self, giant dark oak columns line the walls, arrays of classic novels paint each and every shelf with an essence of deeply held wisdom.

Sweat starts to roll down your brow, you’re looking for just one particular book, “The Secret History Of Genghis Khan”,which i will abbreviate as SHOGK, but how; Where to begin…

This problem doesn’t seem to daunting, but it starts the conversation of “What is the quickest way to find your book; Assuming that this library is well kept and all the books are in order, I propose using the Binary search.

We will start by identifying the beginning and end of the massive shelf, and then with some calculation, we will head to the middle of the shelf. Here we stop and look at the Name of the book; It’s “Eloquent JavaScript” by Marjin Haverbeke, (you should probably grab it, but you don’t)… So now what… Well we need to determine if “SHOGK” comes before or after “Eloquent JavaScript” (alphabetically), it after we will proceed to the right is before we will proceed to the left, scanning as we walk down the line… Pretty Exhausting? Yeah, i don’t know if i made my point yet… either way.. i hope this helped you visualize the binary search, and lets get into the code.

So, here we have a function named binarySearch, this function takes in an Array and a String.

First thing, lets determine where we are. We will determine the front of our array, the end, and with a little math the middle.

Second, what are we looking for? So, While our middle array does not equal our string and our start is not greater than our end, we want to search somewhere else;

Once we find our array that equals our string we want to return the arrays location.

In between we need to determine where to look. So, as soon as we get into our while loop we will check to see if the value of our middle array is greater than or less than our string. If greater than we need to change our endpoint by -1, if the array is less than the string we will need to +1 to out starting point and re evaluate our middle point. this change in the middle point is directing our direction;

We will repeat this sequence until we reach our searching criteria, if we exit the loop without meeting equality, we will return -1 which will signify that the array is not found.

Pretty Simple, just math;

Thanks for bearing with me, and I hope this article brings you value. If you have a better way of solving this Algorithm or Have any questions, feel free to comment below or message me on LinkedIn @ linkedIn.com/adanieljohnson

Here is a sample of the code above, feel free to copy and paste.

function binarySearch(arr, str) {
let start = 0,
end = arr.length - 1,
mid = Math.floor((start + end) / 2);
while (arr[mid] !== str && start < end) {
if (arr[mid] > str) {
end = mid - 1;
} else if(arr[mid] < str) {
start = mid + 1;
}
mid = Math.floor((start + end) / 2);
}
return (arr[mid].toLowerCase() != str.toLowerCase()) ? -1 : mid;
}