binarySearch，lowerBound和upperBou

先从最简单的binarySearch开始。

     
    public static int binarySearch(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }

    private static int binarySearch(int[] nums, int l, int r, int target) {
        while (l <= r) {//[l....r]闭区间查询，l > r 时候形成不了闭区间了，说明没有找到
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {//找到
                return mid;
            } else if (nums[mid] > target) {//说明中间位置太大了，所以要在[l.....mid-1]中继续查找
                r = mid - 1;
            } else {//说明中间位置太小了，所以要在[mid+1 ....r]中继续查找
                l = mid + 1;
            }
        }
        return -1;//跳出循环了没有找到 返回-1
    }

下面我们写的是lower_bound和upper_bound，这两个函数在C++的STL库中是大名鼎鼎的，而JAVA中只有BinarySearch函数，没有这两个函数，而由于这两个方法的算法基础都是binarySearch，所以下面我们动手实现一下，对写出正确的算法和对边界条件的理解都有一定的好处。

lower_bound

nums是一个非降序数组，这个方法将返回数组中第一个大于等于target的元素下标，或者说当target在nums中存在时返回它出现的第一个位置；如果不存在，返回一个下标index：在此处插入target后，仍然使nums中的数字保持有序。

    public static int lowerBound(int[] nums, int target) {// 第一个大于等于target的数的下标
        return lowerBound(nums, 0, nums.length, target);
    }

    private static int lowerBound(int[] nums, int l, int r, int target) {
        while (l < r) {//在[l....r]中查找，l == r时候，夹出来了唯一的位置
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {//中间位置大于等于target，则在[l....mid]中继续查找
                r = mid;
            } else {//中间位置小于target，在[mid+1...r]中查找
                l = mid + 1;
            }
        }
        return l;
    }

上面的代码注意几点：

• 循环条件是l<r，而不是二分搜索中的l<=r
  这是由问题本身决定的，因为在二分搜索中，如果元素不存在，那么就会跳出循环返回-1，这样当l>r时候[l,r]不再是闭区间，可以作为元素不存在返回-1的判定原则，因此l<=r时候循环一直进行。而在lower_bound中，我们并不要求元素一定要存在，不需要判断这个元素是否存在，就算是不存在，我们只需要知道“假设target存在，它应该在的位置",当l==r时候，[l,r]正好能够得到一个唯一的位置，就是我们需要的结果，所以满足l<r让循环一直执行即可。
• 返回值是l或者r
  由于l==r时候终止，所以l和r都可以。
• 查找范围不再是binarySearch的[0......nums.length-1]而是[0......nums.length]
  二分搜索中，我们要求循环在[l,r]闭区间里面找到这个元素那么搜索的范围一定要是每个下标都是在数组内的。而lower_bound就不一样了，一个显而易见的理由就是，有可能在整个数组中都找不到满足条件的下标，也就是nums中所有的值全部小于target，那么我们肯定不能返回nums.length-1，而应该返回最后一个元素后面的位置nums.length。初值应该覆盖所有的可能取值，所以是[0.....nums.length]。

upper_bound

nums是一个非降序数组，这个方法将返回数组中第一个大于target的元素下标，或者说当target存在时返回它出现的最后一个位置的后面一个位置（注意，不是它的出现位置）；如果不存在，返回这样一个下标index：在此处插入target后序列仍然有序。

    public static int upperBound(int[] nums, int target) {// 第一个大于target的数
        return upperBound(nums, 0, nums.length, target);
    }

    private static int upperBound(int[] num, int l, int r,int target) {
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (num[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

和lower_bound的分析方法是一样的，不同点就是nums[mid]>=target那句小小的改变了一下成nums[mid]>target，这也是由问题本身决定的，不再赘述。

下面看剑指上面一个题目：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

这个题可以暴力去解，显然遍历一下是O(n)，不过我们仔细观察可以发现，所谓旋转数组，其实就是由两部分组成，每个部分都是一个非降序的数组，那么我们可以使用二分搜索的思想去解决这个问题，复杂度是O(logn)：

public class Solution {
    public int minNumberInRotateArray(int [] array) {
            int l = 0, r = array.length - 1;//左右两个指针，确定搜索范围[l,r]
            int mid = l;//mid初始化为l，为了防止是排序数组本身的情况，直接返回array[mid]
            while (array[l] >= array[r]) {//由于是非降序数组，所以循环找的条件应该是前面的数字大于等于后面的数字，一定是大于等于，不是大于，因为题目说了非降序而不是升序。
                if (r - l == 1) {//当右指针比左指针大一个时候，说明左指针此时指向第一个递增数组的末尾，第二个指针此时指向第二个递增数组的开头，也就是最小的数字，跳出循环
                    mid = r;
                    break;
                }
                
                mid = l + (r-l)/2;
                                
                if (array[mid]>=array[l]) {//中间数字大于等于左指针数字，那说明mid处于第一个递增数组中
                    l = mid;
                }else if (array[mid] <= array[r]) {//中间数字小于等于右指针数字，那说明mid处于第二个递增数组中
                    r = mid;
                }
            }
            return array[mid];
    }
}

即便说是旋转后的数组不再是有序的，但是它却是由两组有序的数组成的，那么这样就借助二分搜索的思路，在O(logn）解决了这个问题，事实上上述代码是有bug的，如果有好多重复元素，array[l]\array[r]\array[mid]全部等于一个同样的数字，那么无法确定Mid到底处于前半段还是后半段，不过可以确定的是，最小的元素一定在r到l之间，这时候，在[l,r]闭区间O(n)遍历即可。代码优化如下：

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int l = 0, r = array.length - 1;
            int mid = l;
            while (array[l] >= array[r]) {
                if (r - l == 1) {
                    mid = r;
                    break;
                }
                
                mid = l + (r-l)/2;
                
                if(array[l] == array[r] && array[l] == array[mid]){
                    return minInOrder(array, l, r);
                }
                if (array[mid]>=array[l]) {
                    l = mid;
                }else if (array[mid] <= array[r]) {
                    r = mid;
                }
            }
            return array[mid];
    }
    
    public int minInOrder(int [] array, int l, int r){
        int res = array[l];
        for(int i = l+1; i <= r; i++){
            if(array[i] < res){
                res = array[i];
            }
        }
        return res;
    }
}