Kosmos

我以兴趣为饵,钓起生活的大鱼

目录
Leetcode之二分思想
/  

Leetcode之二分思想

友情提示: 代码在这里
本文参照该仓库学习,大家可以star

二分查找

原理

1. 正常实现

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

时间复杂度

二分查找也称为折半查找,每次都能将查找区间减半,这种折半特性的算法时间复杂度为 O(logN)。

m 计算

有两种计算中值 m 的方式:

m = (l + h) / 2
m = l + (h - l) / 2
l + h 可能出现加法溢出,最好使用第二种方式。(竟然是这样,改正)

返回值

循环退出时如果仍然没有查找到 key,那么表示查找失败。可以有两种返回值:

-1:以一个错误码表示没有查找到 key
l:将 key 插入到 nums 中的正确位置

变种

二分查找可以有很多变种,变种实现要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现如下:

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

该实现和正常实现有以下不同:

循环条件为 l < h
h 的赋值表达式为 h = m
最后返回 l 而不是 -1
在 nums[m] >= key 的情况下,可以推导出最左 key 位于 [l, m] 区间中,这是一个闭区间。h 的赋值表达式为 h = m,因为 m 位置也可能是解。

在 h 的赋值表达式为 h = mid 的情况下,如果循环条件为 l <= h,那么会出现循环无法退出的情况,因此循环条件只能是 l < h。以下演示了循环条件为 l <= h 时循环无法退出的情况:

nums = {0, 1, 2}, key = 1
l   m   h
0   1   2  nums[m] >= key
0   0   1  nums[m] < key
1   1   1  nums[m] >= key
1   1   1  nums[m] >= key
...

当循环体退出时,不表示没有查找到 key,因此最后返回的结果不应该为 -1。为了验证有没有查找到,需要在调用端判断一下返回位置上的值和 key 是否相等。

例题

69 求开方

实现 int sqrt(int x) 函数。

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

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

一个数 x 的开方 sqrt 一定在 0 ~ x 之间,并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。

对于 x = 8,它的开方是 2.82842...,最后应该返回 2 而不是 3。在循环条件为 l <= h 并且循环退出时,h 总是比 l 小 1,也就是说 h = 2,l = 3,因此最后的返回值应该为 h 而不是 l。

或者说采用返回x/l 也可以

744 大于给定元素的最小元素

题目描述:给定一个有序的字符数组 letters 和一个字符 target,要求找出 letters 中大于 target 的最小字符,如果找不到就返回第 1 个字符。

540 有序数组的 Single Element

题目描述:一个有序数组只有一个数不出现两次,找出这个数。要求以 O(logN) 时间复杂度进行求解。

令 index 为 Single Element 在数组中的位置。如果 m 为偶数,并且 m + 1 < index,那么 nums[m] == nums[m + 1];m + 1 >= index,那么 nums[m] != nums[m + 1]。

这是由于是偶数对中间插了一个奇数,奇数后面都向后移动一位所以不等于

从上面的规律可以知道,如果 nums[m] == nums[m + 1],那么 index 所在的数组位置为 [m + 2, h],此时令 l = m + 2;如果 nums[m] != nums[m + 1],那么 index 所在的数组位置为 [l, m],此时令 h = m。

因为 h 的赋值表达式为 h = m,那么循环条件也就只能使用 l < h 这种形式。

278 第一个错误的版本

题目描述:给定一个元素 n 代表有 [1, 2, ..., n] 版本,可以调用 isBadVersion(int x) 知道某个版本是否错误,要求找到第一个错误的版本。

如果第 m 个版本出错,则表示第一个错误的版本在 [l, m] 之间,令 h = m;否则第一个错误的版本在 [m + 1, h] 之间,令 l = m + 1。

因为 h 的赋值表达式为 h = m,因此循环条件为 l < h。

153 旋转数组的最小数字

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

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

请找出其中最小的元素。

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

中间值和最后的比较进行范围的缩小

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

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

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

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

两个二分查找


今日诗词 标题:Leetcode之二分思想
作者:ellenbboe
地址:https://zdone.top/articles/2019/04/18/1561009688641.html

评论