Binary search variations/applications

1. find target position, return index, or -1 if not exist

    public int BinarySearch(int[] a, int l, int r, int key) { // find target position 
        while (l <= r) {
            int m = l+(r-l)/2;
            if (a[m] == key)
                return m;
            if (a[m] > key)
                r = m-1;
            else l = m+1;
        }
        return -1;
        }
    }
   

2. find target insert position, return insert index; if target is in the array, the return value is index of the target, if not, return value is the insert position

   this method can be used for both search and insert

    public int BinarySearch(int[] a, int l, int r, int key) { // find target insertion position
        while (l <= r) {
            int m = l+(r-l)/2;
            if (a[m] >= key)
                r = m-1;
            else l = m+1;
        }
        return l;
    }

1. find leftbound of target, return target index; return -1 if not exist

   public int BinarySearch(int[] a, int l, int r, int key) { 
        while (l <= r) {
            int m = l+(r-l)/2;
            if (a[m] >= key)
                r = m-1;
            else l = m+1;
        }
        if (l >= 0 && l < a.length && a[l] == target) {
            return l;
        return -1;
        }
    }
   

2. find rightbound of target, return target index; return -1 if not exist

public int BinarySearch(int[] a, int l, int r, int key) { 
        while (l <= r) {
            int m = l+(r-l)/2;
            if (a[m] <= key)
                l = m+1;
            else r = m-1;
        }
        if (r >= 0 && r < a.length && a[r] == target) {
            return r;
        return -1;
        }
    }

1. find minimum in rotated sorted array

   Without Duplicates

   public class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }    
   
        int left = 0, right = nums.length-1;
   
        while (left <= right) {
            int mid = left + (right-left)/2;
   
            if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) {
                return nums[left];
            }
   
            if (nums[left] <= nums[mid]) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return -1;
    }
   }
   

2. if the target is dynamic, cant find exact equal condition to return

   idea: use an extra variable to store the answer each time

   Example: H index II

public class Solution {
    public int hIndex(int[] citations) {
        int start = 0;
        int end = citations.length-1;
        int len = citations.length;
        int result = 0;
        int mid;
        while(start <= end){
            mid = start + (end-start)/2;
            if(citations[mid] >= (len - mid)){
                result = (len-mid);
                end = mid-1;
            }
            else{
                start = mid + 1;
            }
        }
        return result;
    }
}