Binary Search

1. Search in Rotated Sorted Array（33.leetcode）

• 当 选择 right= nums.length -1 时， while loop 的终止 会是 left < right , 而不是 while(left <= right)
• 解题思路： 只找 连续 increasing 的区间，

public int search(int[] nums, int target) {
    int left  = 0, right = nums.length -1;
    while( left <  right ){
      int mid  = left + (right - left) / 2;
      if(nums[mid]  == target) return true;
      else if( nums[mid] >=  nums[left]){
          if( target < nums[mid] && target >= nums[left] )  right = mid - 1;
          else left = mid + 1;
      } 
      else { // nums[left] >= nums[mid]
          if( target <= nums[ right] && target > nums[mid] ) left = mid - 1;
          else right = mid + 1;
      }
    }
    return nums[left] == target ? left : -1;
}

2. Search in Rotated Sorted Array II（81.leetcode）

• rotated sorted array + duplicate
• 出现duplicate 后， 会导致的 （left > mid ? ）无法判断连续ascending 的区间，
• 解题办法： 去重 ， 把pointer 移动到 和mid element 不一样的element 上

public boolean search(int[] nums, int target) {
    int left = 0 , right = nums.length - 1;
    while( left <= right){
        int mid = left + (right - left)/2;
        if( nums[mid] == target) return true;
        if( nums[left] == nums[mid]) left ++;
        else if( nums[left] < nums[mid]) {
            if( target >= nums[left] && target < nums[mid] ) right = mid -1 ;
            else left = mid + 1;
        }else{ // nums[left] > nums[mid]
            if( target <= nums[right] && target > nums[mid]) left = mid + 1;
            else right = mid - 1;
        }
    } // while
    return false;
}

3. Find Minimum in Rotated Sorted Array（153.leetcode）

public int findMin(int[] num) {
    if(num == null || nums.length == 0) return 0;
    intleft = 0, right = num.length - 1;
    while( left < right ){
        int mid  = left + (rigth - left)/2;
        if(num[mid] < num[right]) right = mid;
        else if( num[mid] > num[right]) // min in the right part
            left = mid - 1;
     }
      return num[left];
}

4.Search Insert Position（ 35.leetcode）

public int searchInsert(int[] nums, int target) {
    if(num == null || num.length == 0) reutn 0;
     int left = 0, right = num.length - 1;
     while( left <= right ){
          int mid = left + (right - left)/2;
          if( num[ mid] == target) return mid;
          if(num[ mid] < target ) left = mid + 1;
          else if ( num[mid] > target)  right = mid - 1;
      }
      return left;
}

5.Two Sum II - Input array is sorted（278.leetcode）

public int firstBadVersion(int n) {
    int start = 1, end = n;
    while (start < end) {
        int mid = start + (end-start) / 2;
        if (!isBadVersion(mid)) start = mid + 1;
        else end = mid;            
    }        
    return start;
}

6. Intersection of Two Arrays II (350.leetcode）

-**解题思路： ** 要比较2个array 的话， 各用一个pointer

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int[] res = new int[ Math.max( nums1.length , nums2.length)];
    int left = 0, right = 0, used = 0;
    while( left < nums1.length && right < nums2.length ){
         if( nums1[left] == nums2[right]){
              left ++, right ++;
              res[used ++] = nums1[left];
         }
        else if( nums1[left] < nums2[right]) left ++;
        else right ++:
    }
return Arrays.copyOf(ans, used);
}

7 . (350.leetcode）