Binary search explain in Javascript

Introduction

It is also called, half interval search. Usually done by placiong two pointers at start and end. Cut in half the looking range, until locating the target.

Time Complexity

Let’s say we have range of N, and it takes X times we can cut the range in half and get the Target.

1 = N / 2^x

multiply by 2x:

2x = N

now do the log2:

log2(2x) = log2 N
x * log2(2) = log2 N
x * 1 = log2 N

this means you can divide log N times until you have everything divided. Which means you have to divide log N (“do the binary search step”) until you found your element.

What is Two Pointer and BInary Search? What’s the relationship between them?

Simply put. Binary Serach is an algorithm. Two Pointers is an approach to achieve it.

Besides solving BS, TP can be really good to determine if a loop exist in an array or linked-list,

Imagining a faster pointer (move 2 index each teration) and a slower pointer (move 1 index each teration).

The faster pointer can always catch up slower pointer if a loop exists.

Leetcode Example

69. Sqrt(x)

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if(x===0)return 0    
    let [i, j] = [1, x]
    let ans;

    while(i<=j){
        let mid = (i+(j-i)/2) << 0

        if(mid<=x/mid){
            ans = mid
            i = mid + 1
        }
        else{
            j = mid -1
        }
    }
    return ans
};

744. Find Smallest Letter Greater Than Target

var nextGreatestLetter = function (letters, target) {
      let [start, end, mid] = [0, letters.length - 1, -1];

      while (start <= end) {
            mid = Math.floor(start + (end - start) / 2);

            if (target < letters[mid]) {
                  end = mid - 1;
            } else {
                  start = mid + 1;
            }
      }
      return letters[start % letters.length];
};

153. Find Minimum in Rotated Sorted Array

var findMin = function(nums) {
    let [i, j] = [0,nums.length-1]
    while(i<j){
        let mid = i+ Math.floor((j-i)/2)
        if(nums[mid]>nums[j]){
            i = mid+1
        }
        else{
            j=mid
        }
    }
    return nums[i]

};