Binary Search

“Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.”

Binary search is faster than linear search, the time complexity of binary search is O(logN) but it’s O(N) for linear search.

Template and Explanation

We use a while loop while (l <= r)to shrink the range of our search until we find a match or l>r we break out of the loop.

To find the middle of l and r, we used m = Math.floor(l + (r — l)/ 2) instead of Math.floor((l+r)/2) . The reason is to prevent overflow. If r is already the largest number Javascript can handle, when you add l to it, the sum of l and r will cause overflow and the number you get from (l+r)/2 would not be the one you wanted.

if(condition1: m is the answer) return m this is for situation where we need to find the exact match (e.g. given [1,2,3,4,5], return the index number of 3).

So here we have condition2 to help us decide whether we should check the left or right side of the array. And in the end we will return the smallest l to make condition2 true.

For example, given array let arr = [1,3,5,7,9], we want to find the smallest number in the array that is larger than the input number let input = 6. We will write:

iterate through the array:

Example for practice

Cases varies, we can use template to help us but we have to understand what the question is asking for and adjust the template to get the result we want.

Resources: