二分搜索

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

【解法1】二分查找 轮着每行查

【解法2】直接查找 从矩阵的左下角看，上方的数字都比其小，右方的数字都比其大，所以依据该规律去判断数字是否存在 设当前数字为 cur，目标数字为 target，当 target < cur 时，cur 更新为其上面的数字，当 target > cur 时，cur 更新为其右侧的数字，直到相等则返回 true，否则到了矩阵边界返回 false 时间复杂度：

public boolean findNumberIn2DArray(int[][] M, int target) {
    int n = M.length;
    if(n == 0) return false;
    int m = M[0].length;
    int i = n-1, j = 0;
    while(0 <= i && i < n && 0 <= j && j < m){
        if(M[i][j] == target) return true;
        else if(M[i][j] > target) i--;
        else j++;
    }
    return false;  
}

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

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

题目是用二分法，case有三种情况

如上图所示，输入的情况跟右端点比较。如果数组中的元素都一样则right--，因为数组是升序的，所以最小值一定靠近左侧，而不是右侧

public int minArray(int[] numbers) {
    int n = numbers.length;
    int left = 0, right = n-1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(numbers[mid] < numbers[right]){
            right = mid;
        }else if(numbers[mid] > numbers[right]){
            left = mid + 1;
        }else{
            right--;
        }
    }
    return numbers[left];
}