二分查找算法一般要求数组是有序的，应用过程中必须要设置一个基准值，用数组中间部位的值与基准值比较进而更新查找区间。

二分查找算法的基本框架：

public int searchNum(int[]nums,int target){
    int l=0;
    int r=nums.length-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(nums[mid]==target){
            return mid;
        }else if(target<nums[mid]){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return -1;//表示没有找到该数字
}

二分查找算法的边界问题：

情况1：在区间[left,right)内使用二分查找算法寻找答案，注意这里的区间是左闭右开的。在更新right时，只能是right=mid,其中mid=left+(right-left)/2。

那么为什么不能是right=mid-1呢？理由很简单，假设将right更新为mid-1，则查找区间变成了[left,mid-1),因为右边是开区间，所以mid-1是查找不到的，而更新right之前只能说明索引mid处不是我们要查找的答案，并不能说明mid-1处也不是正确答案，mid-1处仍然是要考虑的。总之，开区间的一侧一定不能缩小区间。而left要更新为mid+1,才能保证区间里的每个元素都能被访问到。

情况2：在[left,right]内使用二分查找寻找答案，这里是左闭右闭的区间。根据情况1的分析可知更新区间应为：left=mid+1,right=mid-1,可以保证区间里的每个元素都能被访问到。

经过上述分析，可以说运用二分查找算法的总体流程应分为3个步骤：

1、确定基准值，将这一步骤单独拿出来主要是为了针对二分查找算法的一些变体。

2、确定查找区间，及区间的更新方式。

3、调试结果。

1、旋转数组中的最小数字

JZ6题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

示例：

输入
[3,4,5,1,2]
返回值
1

解答：

本题考查二分查找算法的灵活运用，有序数组旋转后会变成两部分有序的数组。

本题的基准值设置为查找区间最右边的值，那能不能将左左边的值设置为基准值呐，答案是不能的，理由如下，假如有一个数组为[1,2,3,4,5]，基准值target=1,中间值mid=3,此时mid是大于基准值的，这种情况下答案1在mid的左边。现有另一数组[3,4,5,1,2],基准值target=3,中间值mid=5,mid仍然是大于基准值的，而这种情况下答案1却在mid的右边。意思是将基准值设置在最左边，对于同样中间值大于基准值的情况，会出现两种情况，有时候答案在左部分，有时候却在右部分，因此无法正确更新查找区间。

public int minNumberInRotateArray(int [] array){
        //一定要选择最右边的元素作为基准值
        int left=0;
        int right=array.length-1;
        if(right<0)return 0;
        //int target=array[right];
        while(left<right){
            int mid=left+(right-left)/2;
            if(array[mid]>array[right]){
                left=mid+1;
            }
            else if(array[mid]<array[right]){
                right=mid;
            }
            else{
                //如果是 1 0 1 1 1， arr[mid] =    target = 1, 显然答案在左边
                //如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
                //所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案。
                 right--;
            }
        }
        return array[right];
    }

2、二维数组中的查找

JZ1题目描述：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

输入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true

解答：

该二维数组每一行和每一列中的元素都是递增排列的，因此可以使用二分查找算法的思想来查找元素。运用二分查找算法的时候，选定的中间值mid必须满足整体有序的，即在上述示例中可以选择array[0] [3]作为中间值mid， 该mid值所在行是递增的，所在列也是递增的。

public class Solution {
    //对二维有序数组进行二分查找
    public boolean Find(int target, int [][] array) {
        int row=array.length;
        if(row==0) return false;
        int col=array[0].length;
        int i=0;int j=col-1;
        while(i<row&&j>=0){
            if(target>array[i][j]){
                i++;
            }
            else if(target<array[i][j]){
                j--;
            }
            else{
                return true;
            }
        }
        return false;
    }
}

3、查找左右边界

假设有一个有序数组{1,2,2,2,3}，这个时候让你查找target=2的边界，便可以使用二分查找算法来分别查找有序数组的左右边界。

查找左边界：

public int findLeftBound(int[] nums,int target){
    int left=0;
    int right=nums.length-1;
    while(left<right){//注意：区间对应
        int mid=left+(right-left)/2;
        if(target<=nums[mid]){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}

查找右边界：

public int findRightBound(int[] nums,int target){
    int left=0;
    int right=nums.length-1;
    while(left<right){注意：区间对应
        int mid=left+(right-left)/2;
        if(target<nums[mid]){
            right=mid-1;
        }
        else{
            left=mid;
        }
    }
    return right;
}