Binary Search

Easy

1. A simple binary search

   let l=0, r=n-1;
    
   while(l<=r) {
   	let mid = l + Math.floor((r-l)/2);
   	if(nums[mid] == target) {
   		return mid;
   	} else if( nums[mid] > target ) {
   		r = mid-1;
   	} else {
   		l = mid+1;
   	}
   } 
    

2. Upper bound / Lower bound Lower Bound: Index greater than or equal to the target.

   • If mid is greater move towards left, but this could be the answer if no equal present, so do r=mid, and not r=mid-1. Also, do l < r, otherwise it will not come out of loop if there’s an equal to target present.

   while(l<r) {
   	let mid ...
    
   	if(nums[mid] >= target ) {
   		r = mid;
   	} else {
   		l = mid+1;
   	}
   }
    
   return l;
    

   Upper Bound: First index strictly greater than x

   • Even if smaller than target, keep moving right, since need greater than strictly, just to l = mid + 1

   while(l<=r) {
   	let mid ...
   	
   	if(nums[mid] <= target) {
   		l = mid+1;
   	} else {
   		r = mid-1;
   	}
   }
    
   return l;
    

3. Search in rotated

   • Don’t first find the pivot and then search. Instead in the BS itself, check which part is sorted, set the l or r and then search in the sorted part.
   • If duplicates are there. The hard part is when, left, mid and right are same, then can’t find the sorted, so skip it while( left == mid && right == mid ) l++; r--;