# Binary Search

**Binary Search**

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.