LeetCode 搜索旋转排序数组/寻找旋转排序数组中的最小值[二分查找]-一一网

这是我参与更文挑战的第 11 天，活动详情查看：更文挑战

寻找比目标字母大的最小字母（744）

题目描述

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'

示例 1：

输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"

输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"

输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f"

输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j"

输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c"

输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"
复制代码

提示

letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成，最少包含两个不同的字母。
目标字母target 是一个小写字母。

思路分析

寻找比目标字母大的最小字母，目标字母可能不在已排序后的字符列表中，所以如果目标字母小于排序的首字母，那么直接返回；我们使用二分查找，因为字符列表已经排好序了。如果目标字母等于其中的某个字母，那么我们一直找到大于该字母的最小字母。

二分查找有一定的套路，首先定义 low 和 high，while 循环的判断条件一直是 low <= high，对于 low == high，必要的时候特殊处理，在 while 内部补充，返回值永远是 mid；low、high 的更新永远是 low = mid + 1 和 high = mid – 1；

对于非确定性的查找，使用前后探测法，来确定搜索区间。先处理命中情况，再处理左右半部分查找的情况。

代码展示

解法一：时间复杂度是 ${O(logn)}$ ，空间复杂度是 ${O(1)}$ 。

public char nextGreatestLetter(char[] letters, char target) { // a b c d     c
        int low = 0;
        int high = letters.length - 1;
        while (low <= high){
            int mid = low + (high - low)/2;
            if ((mid == 0 || letters[mid - 1] <= target) && letters[mid] > target){
                return letters[mid];
            } else if (target > letters[mid]){
                low = mid + 1;
            } else if (target < letters[mid]){
                high = mid - 1;
            } else if(letters[mid] == target){
                low = mid + 1;
            }
        }
        return letters[0];
    }
复制代码

搜索二维矩阵（74）

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
复制代码

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
复制代码

提示

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

思路分析

这道题也是使用二分查找，难点在于我们需要处理一下二维矩阵的二分查找，进行二分的时候，行的索引是 mid/n，列的索引是 mid%n；后续的处理就和普通的二分查找没什么区别了。

代码展示

解法一：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(1)}$ 。

		//[[1, 3 ,5, 7]
    // [10,11,16,20]
    // [23,30,34,60]],    5
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length; //3
        int n = matrix[0].length; //4

        int low = 0;
        int high = m * n - 1;
        while (low <= high){
            int mid = low + (high - low)/2;  //5
            int i = mid / n;  //行
            int j = mid % n;       //列
            int value = matrix[i][j];
            if (target == value){
                return true;
            } else if (target > value){
                low = mid + 1;
            } else {
                high = mid - 1;
            }


        }
        return false;
    }
复制代码