二分查找

剑指 Offer 11. 旋转数组的最小数字

myself

 public int minArray(int[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < numbers[i - 1]){
                return numbers[i];
            }
        }
        return numbers[0];
    }

题解思路：

排序数组的查找问题首先考虑使用二分查找解决，其可以将遍历法的线性级别时间复杂度降低至对数级别

算法流程

1、初始化：声明i，j双指针分别指向nums数组左右两端
2、循环二分：设m=（i+j）/2为每次二分的中点，那么此时可能出现三种情况：
1、nums[mid] >nums[j]时，此时数组的最小值可能出现的区间缩减至【mid+1，j】
2、nums[mid]3、nums[mid]=nums[j]时，此时说明区间[mid，j]之间的值都是相等的或者[ ]，而需要找到的是最前的，可以将j—缩小区间

class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            //满足这个判断条件说明右半边的区域是不正常的
            if (numbers[m] > numbers[j]) i = m + 1;
            //满足这个判断条件说明左半边的区域是不正常的
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}

实际上，当出现nums[m]=nums[ j ]时，一定有区间[i，m]内所有元素相等或者区间[m，j]内所有元素相等（或两者都满足）。对于寻找此类数组的最小值问题， 可直接放弃二分查找，使用线性查找代替。

public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int mid = (i + j) / 2;
            if (numbers[mid] > numbers[j]) {
                i = mid + 1;
            } else if (numbers[mid] < numbers[j]) {
                j = mid;
            } else {
                int x = i;                                    *
                for (int k = i + 1; k < j; k++) {
                    if (numbers[k] < numbers[x])   
                        x = k;
                }
                return numbers[x];
            }
        }
        return numbers[i];
    }

总结： 此处的退化为线性搜索并不是一开始我所想的那样的从头到尾的相邻的值的比较，而是始终在和第一个值比较 而且这里的比较其实只能用右边的比较，如果你用左边的元素来操作的话就会出现正常递增的数组无法得到正确的解。

53. 数字在排序数组中出现的次数

题解思路：
找到给定数字k在有序数组第一个位置和最后一个位置，就可以找到该数字出现的次数。
先考虑如何实现寻找在有序数组的第一个位置。正常的二分查找如下，在查找到给定元素k之后，立即返回当前索引下标

public int binarySearch(int[] nums,int k){
    int l=0,h=nums.length-1;
    while(l<=h){
        int m=l+(h-l)/2;
        if(nums[m]=k){
            return m;
        }else if(nums[m]>k){
            h=m-1;
        }else{
            l=m+1;
        }
    }
    return -1;
}

但是在查找第一个位置时，找到元素之后应该继续往前找。也就是当 nums[m]>=k 时，在左区间继续查找，左区间应该包含 m 位置。

private int binarySearch(int[] nums, int K) {
    int l = 0, h = nums.length;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] >= K)
            h = m;
        else
            l = m + 1;
    }
    return l;
}

查找最后一个位置可以转换成寻找 k+1 的第一个位置，并再往前移动一个位置。

public int GetNumberOfK(int[] nums, int K) {
    int first = binarySearch(nums, K);
    int last = binarySearch(nums, K + 1);
    return (first == nums.length || nums[first] != K) ? 0 : last - first;
}

需要注意以上实现的查找第一个位置的 binarySearch 方法，h 的初始值为 nums.length，而不是 nums.length - 1。先看以下示例：

nums = [2,2], k = 2

如果 h 的取值为 nums.length - 1，那么在查找最后一个位置时，binarySearch(nums, k + 1) - 1 = 1 - 1 = 0。这是因为 binarySearch 只会返回 [0, nums.length - 1] 范围的值，对于 binarySearch([2,2], 3) ，我们希望返回 3 插入 nums 中的位置，也就是数组最后一个位置再往后一个位置，即 nums.length。所以我们需要将 h 取值为 nums.length，从而使得 binarySearch 返回的区间更大，能够覆盖 k 大于 nums 最后一个元素的情况。