Binary Search

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

var binarySearch=function(l, r){
  while (l <= r){
    m = Math.floor(l + (r - l)/ 2) //find the middle of l and r
    if(condition1: m is the answer) return m    //optional
    
    if(condition2: need to check left side){ 
      r = m - 1       //check left side of m, new range [l, m - 1]    
    }else{
      l = m + 1       //check right side of m, new range [m+1, r]
    }        
  }
    return l        //find smallest l to make condition2 true     
}

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).

 if(condition2: need to check left side){ 
      r = m - 1       //check left side of m, new range [l, m - 1]    
 }else{
      l = m + 1       //check right side of m, new range [m+1, r]
 }        
}//closing bracket of the while loop
    return l        //find smallest l to make condition2 true

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:

var findSmallestNumberLargetThanInput=function(arr, l, r, input){
  
  while (l <= r){
    m = Math.floor(l + (r - l)/ 2)
    if(arr[m] > input){
       r = m - 1
    }else{
       l = m + 1
    }       
  }
  return arr[l]               
}

iterate through the array:

      l r m  //if(arr[m] > input), check left, else check right
index 0 4 2  //arr[2] = 5, 5<6, check the right side, l = m + 1 = 3 
index 3 4 3  //arr[3] = 7, 7>6, check the left side, r = m - 1 = 2
index 3 2 3  // l > r, break out of loop, return arr[3] = 7

Example for practice

var mySqrt = function(x) {
    if (x < 2) return x;
    
    let left = 2
    let right = x
    
    while(left<=right){
      let mid = Math.floor(left + (right - left)/2)
      if(mid>x/mid){ //prevent overflow
          right = mid - 1
      }else{
          left = mid + 1
      }
    }
    return left - 1 // we find the smallest left that match    //mid>x/mid, then return left - 1 to find the square root.
};

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:

Binary search algorithm

Binary Search - GeeksforGeeks