D8bbb2ee4334cbeb44ef08d339c9c2fd
leetcode高频题——二分查找

[TOC]

概述

本文是从leetcode题库中精选出的关于二分查找的题目,在面试中具有较高的出现频率。

二分查找

首先我们先来看一下二分查找,二分查找解决的问题是,在有序数组中查询目标数字的位置,java jdk提供了二分查找方法,我们可以阅读一下源码(jdk1.8.0_211):

private static int binarySearch0(char[] a, int fromIndex, int toIndex,
                                 char key) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        char midVal = a[mid];
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

可以看到,如果目标数字key存在,该方法将会返回目标数字在数组中的位置,如果不存在,将返回一个负数,使用二分查找的关键是目标数组有序

69. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
思路:
这道题是一个二分法的变形,值得注意的是最后返回值是high而不是low,原因是在不满足while条件,程序跳出循环时,high的值要小于low,所以此时应该返回high。
代码:

class Solution {
    public int mySqrt(int x) {
        if(x < 2){
            return x;
        }
       int low = 1;
       int high = x;
       while(low <= high){
           int mid = low + (high - low)/2;
           int sqrt = x / mid;
           if(mid == sqrt){
               return mid;
           }else if(mid < sqrt){
                low = mid + 1; 
           }else{
                high = mid - 1;
           }
       }
       return high;
    }
}

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 是一个小写字母。
思路:
这道题根据示例可以看出,如果给出的letters没有比target大的最小字母,则返回letters中的第一个字母。
代码:

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int low = 0;
        int high = letters.length - 1;
        while(low <= high){
            int mid = low + (high - low)/2;
            if(letters[mid] <= target){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return low < letters.length? letters[low]: 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)空间复杂度中运行。
思路:
这道题是二分法中比较有趣的一道题,首先通过阅读题干,我们可以知道如下几个信息:
1. 数组有序
2. 重复元素出现2次
3. 要求时间复杂度为O(log n),空间复杂度为 O(1)

我们根据 条件(1)和条件(3),可以知道,这应该是一道二分法的题(如果没有条件3,那么这道题可以用异或来解,代码会非常简单),我们可以利用条件(2),确定二分法中的mid,这里值得注意的是,我们在划分查找区间的时候,要包含所有相同的数字(比如1 ,2,2,3,3 可以划分成 1,2,2和3,3 不能划分成 1,2,2,3和3),那么划分出来的数组,如果含有目标数字,那他的长度一定是奇数(可以通过nums[mid]和nums[mid+1]是否相等来确定数组长度的奇偶,因为mid为偶数。如果nums[mid] != nums[mid+1]那么[low,mid]的长度就是奇数,所以目标数字就在这个区间内),我们可以通过这个方法,不断的二分求值。
代码:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high){
            int mid = low + (high - low)/2;
            if(mid % 2 == 1){
                // 保证了查找区间一值是奇数
                mid--;
            }
            if(nums[mid] == nums[mid+1]){
                low = mid + 2;
            }else{
                high = mid;
            }
        }
        return nums[low];
    }
}

278. 第一个错误的版本

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
思路:
这是一道[应用题],我们通过分析可得,这是一道标准的二分法类型题
代码:

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int low = 0, high = n;
        while(low < high){
            int mid = low + (high - low) / 2;
            if(isBadVersion(mid)){
                high = mid;
            }else{
                low = mid + 1;
            }
        }
        return low;
    }
}

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
思路:这里我们要注意题干给出的条件:数组中不存在重复元素,我们将示例1中的数据用坐标轴表示出来,便于观察数据。

我们可以看出,第一段数据的最小值大于第二段数据的最大值,所以我们可以选一个值(记作A)和边界值(本题我们选取数组的右边界值)进行比较。
如果A值小于边界值,则说明A点在第一段数据上,此时目标值就在[A,right]之间
如果A值大于边界值,则说明A点在第二段数据上,此时目标值就在[left,A]之间
代码:

class Solution {
    public int findMin(int[] nums) {
        int left = 0,right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] <= nums[right]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

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]
思路
根据题干可知:这是一道二分法的题(数组有序,时间复杂度要求O(log n)),其实这里隐含两种二分法的实现:
1 求目标数值第一次出现的位置
2 求目标数值最后一次出现的位置
所以我们可以写两个二分法函数进行求解,但是我们也可以换一种思路:
1 求目标数值第一次出现的位置
2 求目标数值+1第一次出现的位置 - 1
这样我们就可以只写一个方法去解决这个问题。
代码:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        int last = findFirst(nums, target + 1) - 1;
        if(first == nums.length || nums[first] != target){
            return new int[]{-1, -1};
        }else{
            return new int[]{first, last};
        }
    }

    private int findFirst(int[] nums, int target){
        int low = 0,high = nums.length;
        while(low < high){
            int mid = low + (high - low) / 2;
            if(target <= nums[mid]){
                high = mid;
            }else{
                low = mid + 1;
            }
        }
        return low;
    }
}

如果有不明白的题,请在本文下面留言,博主会单独做动画演示
最后,期待您的订阅和点赞,同时也期待您的批评与指正!

© 著作权归作者所有
这个作品真棒,我要支持一下!
一个坚持原创的小专栏。分享编程知识,提升工作效率,致力于通过简单的语言,把编程这点事讲清楚。涵盖内容:java、设...
0条评论
top Created with Sketch.