Binary Search is one of the simplest algorithms to learn. All we have to do is take the center value in a sorted list and check if it fits the criteria of what we are looking for. If it does not shift the range of what you are looking for to the left or right of the center value. Here is some basic code to look for 10 in a sorted array.
function binarySearch(arr) { let low = 0; let high = arr.length - 1; while (low <= high) { let mid = Math.floor((high + low) / 2); if (arr[mid] === 10) { return mid; } else if (arr[mid] < 10) { low = mid + 1; } else { high = mid - 1; } } return -1}
This looks like a simple and easy solution, however, there is a problem with what we have here. The largest integer that javascript can handle is 1.7976931348623157e+308. This is an extremely large integer, but you could run into problems if the low and high values combine to a number larger than this. To keep this from happening you should change the function for mid to be, “mid = low + (high — low) / 2,” this will allow our program to work with a larger set of data.
Now that we understand the base case for binary search we can try to think of other use cases for this algorithm. What if we wanted to find the first number in a list that was greater than or equal to a specific number. All you need to do is rearrange then algorithm and store the output and you will have what you need.
function binarySearchFirst(arr, num) { let first = -1 let low = 0; let high = arr.length - 1; while (low <= high) { let mid = Math.floor(low + (high - low) / 2); if (arr[mid] >= num) { first = mid high = mid - 1 } else { low = mid + 1; } } return first}
There are many other use cases for this seemingly simple algorithm. Though Binary Search is simple it is important to understand it not just memorize it so that you are able to refactor and use this algorithm in a variety of situations.
