二分查找搜索

LeetCode

发布日期: 2019-04-16

文章字数: 1.8k

阅读时长: 7 分

阅读次数:

二分查找有很多变种应用，关键在于以下三点

循环条件的设置
边界选取（指针更新表达式）
返回值

69. x 的平方根

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解题思路

sqrt(x)肯定是1~x之间的一个数，并且满足sqrt = x/sqrt，所以我们把要找的mid值每次与x/sqrt比较

循环条件
l <= h
如果不取等，会造成结果偏大
边界选取
常规操作
返回值
h
在循环条件为 l <= h 并且循环退出时，h 总是比 l 小 1

public int mySqrt (int x) {
    if (x <= 1)
        return x;
    int l = 1, h = x;
    while (l <= h) {
        int mid = l + (h - l) / 2;
        int sqrt = x / mid;
        if (mid == sqrt) {
            return mid;
        } else if (mid > sqrt) {
            h = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return h;
}

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

题目描述

给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子，如果目标字母target = 'z'并且有序数组为 letters = ['a', 'b']，则答案返回 'a'。

示例:

输入:
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 是一个小写字母。

解题思路

循环条件的设置
l <= h

边界选取（指针更新表达式）

if (letters[m] <= target) 
    l = m + 1;

使结果偏右

返回值

return l < n ? letters[l] : letters[0];

超出索引则返回第一个元素

public char nextGreatestLetter (char[] letters, char target) {
    int n = letters.length;
    int l = 0, h = n - 1;
    while (l <= h) {
        int m = l + (h - l) / 2;
        if (letters[m] <= target) {
            l = m + 1;
        } else {
            h = m - 1;
        }
    }
    return l < n ? letters[l] : letters[0];
}

540. 有序数组中的单一元素

题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

解题思路

循环条件的设置
l<h
因为边界选取为 h = m,所以不能取等
边界选取（指针更新表达式）
如果 nums[m] == nums[m + 1]，那么 index所在的数组位置为 [m + 2, h]，此时令 l = m + 2；如果 nums[m] != nums[m + 1]，那么 index所在的数组位置为[l, m]，此时令 h = m。
返回值
nums[l]

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

278. 第一个错误的版本

题目描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

解题思路

指针更新
- 如果第 m 个版本出错，则第一个出错版本在[l, m]，令h = m；
- 如果第 m 个版本不错，则第一个出错的版本在[m+1, h]，令l = m+1
循环条件

l < h

因为指针更新表达式为h = m所以不能取等
返回值
l

public int firstBadVersion(int n) {
    int l = 1, h = n;
    while (l < h){
        int m = l + (h - l)/2;
        if(isBadVersion(m) == true)
            h = m;
        else 
            l = m + 1;
    }
    return l;
}

153. 寻找旋转排序数组中的最小值

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

解题思路

边界选取（指针更新表达式）
nums[m] <= nums[h]说明最小值在[l,m]
循环条件的设置
h = m则不能取等
返回值
nums[l]

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

34. 在排序数组中查找元素的第一个和最后一个位置

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解题思路

先通过辅助方法，找到元素第一次出现的位置，这个位置上的元素正好就是我们要找的target，也可能是比target大的元素（数组中没有target时）。在判断high指针的位置时，判断条件中没有nums[mid] = target，使得high指针总是倾向于往左移，从而能确保找到第一次出现的位置。

再找target第二次出现的位置，第二次出现的位置可以通过找到target+1的位置再减一得到。

public int[] searchRange(int[] nums, int target) {
    int start = firstGreaterEqual(nums, target);
    if (start == nums.length || nums[start] != target){
        return new int[] {-1,-1};
    }
    return new int[] {start,firstGreaterEqual(nums,target + 1)-1};
}

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