二分法的宗旨，在于每次搜索的时候舍弃了解不在的那一半，最后将区间缩小并逼近解。不仅是全集有序可以使用，分段有序也可以使用。
二分法算法框架

int[] nums = {};
int target = 0;
int start = 0;
int end = nums.length - 1;
while(start < end){
  int mid = (end - start)/2 + start;
  if(target > nums[mid]){
    start = mid + 1;
  }else if (target < nums[mid]){
    end = mid - 1;
  }else{
    break;
  }
}
}

我们知道两个数的中位数，可以使用Δx/2 + x，也可以(x1+x2)/2；但是出于极端的考虑，x1+x2有可能出现Integer或者long越位，所以推荐使用Δx/2 + x。

33. Search in Rotated Sorted Array

给定一个有序数组的任意次右移结果，找出某个元素的位置，不存在返回-1。
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2])。

image.png

在确定分段有序的时候，如果target在此范围内，就缩小到此范围，否则就使用另外一半区间。

    public static int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length-1;
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[start] <= nums[mid]){
                if(target >= nums[start] && target < nums[mid]){
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }
            }else {
                if(target > nums[mid] && target <= nums[end]){
                    start = mid + 1;
                }else{
                    end = mid -1;
                }
            }
        }
        return -1;
    }

81. Search in Rotated Sorted Array II

这是上一题有duplicate的升级。

image.png

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

154. Find Minimum in Rotated Sorted Array II

在一个旋转数组中找出最小值。
2,2,2,0,1为例
（1）找到中间位置，中间位置[2]没有[1]大，则start区间前进到mid，此时start=2,end=4
（2）找到中间位置，中间位置[0]比[1]要小，则end缩短至mid，此时start=2,end=3
（3）结束，比较2，3位置取最小值
如果mid位置等于end位置，则end直接往前移动一个位置。

image.png

    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        while(start < end-1){
            int mid = (end - start) / 2 + start;
            if(nums[mid] < nums[end]){
                end = mid ;
            }else if (nums[mid] > nums[end]){
                start = mid ;
            }else{
                end --;
            }
        }
        return Math.min(nums[start],nums[end]);
    }