一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 11554|回复: 41
收起左侧

[二分/排序/搜索] Binary Search的总结帖

    [复制链接] |只看干货 |刷题, 二分/排序/搜索
我的人缘0

分享帖子到朋友圈
本楼: 👍   93% (15)
 
 
6% (1)   👎
全局: 👍   95% (123)
 
 
4% (6)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
# 公瑾总结

本总结参考/复制/修改了很多综合帖的内容,全部参考文档会赋予文章底部。
作者:公瑾
转载请注明出处:https://github.com/yuzhoujr/leetcode

## Binary Search | 基础
> 用途:**针对Sorted数组查找的算法**
> 时间复杂度: O(log(n))

二分查找法的前置条件要拥有一个已经Sorted好的序列,这样在查找所要查找的元素时, 首先与序列中间的元素进行比较, 如果大于这个元素, 就在当前序列的后半部分继续查找, 如果小于这个元素, 就在当前序列的前半部分继续查找, 直到找到相同的元素, 或者所查找的序列范围为空为止.

> 伪代码:

```
left = 0, right = n -1
while (left <= right)
    mid = (left + right) / 2
    case
        x[mid] < t:    left = mid + 1;
        x[mid] = t:    p = mid; break;
        x[mid] > t:    right = mid -1;
return -1;
```
<br><br>

## Binary Search | 痛点

> **十个二分九个错**:编程珠玑的作者Jon Bentley,布置作业让他的学生们写二分查找,然后他一个个来看。结果呢,他发现90%是错的。

按照上面的伪代码写出了下列的Python代码
```
def binarySearch(arr, target):
    l , r = 0, len(arr) - 1  
    while l <= r:            
        mid = (l+r)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1
        else:
            r = mid - 1
    return -1
```

接下来说说二分查找的一些痛点。

#### 痛点1:  溢出
> `mid = (l+r)//2`

在对两个Signed 32-bit数字进行相加时,有可能出现**溢出**,例如下面这种情况:
> left = 1, right = Integer.MAX_VALUE

当left 与 right 之和超过了所在类型的表示范围的话, 这个和就会成为一个很随机的值, 那么 middle 就不会得到正确的值.
所以, 更稳妥的做法应该是这样的
> `mid = l + (r-l)//2`

<br><br>


#### 痛点2: 边界错误

二分查找算法的边界, 一般来说分两种情况, 一种是左闭右开区间, 类似于 [left, right), 一种是左闭右闭区间, 类似于 [left, right].

等等,区间是个什么鬼,左闭右开,左闭右闭又是个什么鬼?

> 区间的定义: 区间有开区间和闭区间,其中又分为全开区间(  ),全闭区间[   ],左开右闭区间(     ] 和左闭右开区间 [  ),开区间的意思是区间两处的端点值取不到,而闭区间的端点值就可以取到。
例如区间[2,6),他是一个左闭右开的区间,那么在这2~6之间的数字我都可以取到,而且可以取到2,但不可以取到6.

需要注意的是, 循环体外的初始化条件, 与循环体内的迭代步骤, 都必须遵守**一致的区间规则**, 也就是说, 如果循环体初始化时, 是以左闭右开区间为边界的, 那么循环体内部的迭代也应该如此. 如果两者不一致, 会造成程序的错误. 比如下面就是错误的二分查找算法:

```
def binarySearch(arr, target):
    l , r = 0, len(arr)
    while l < r:            
        mid = (l+r)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1
        else:
            r = mid - 1
    return -1
```
这个算法的错误在于, 在循环初始化的时候, 初始化 r=len(arr), 也就是采用的是左闭右开区间, 而当满足 target < arr[mid] 的条件是, target 如果存在的话应该在 [left, mid) 区间中, 但是这里却把 r 赋值为 mid - 1 了, 这样, 如果恰巧 mid-1 就是查找的元素, 那么就会找不到这个元素.
下面给出两个算法, 分别是正确的左闭右闭和左闭右开区间算法, 可以与上面的进行比较:

**左闭右闭:包括End区间,end inclusive**
```
def binarySearch(arr, target):
    '''
    定义:在[l...r]的范围里寻找target, 因为这里定义是需要将r归入范围区间, inclusive,所以while循环的边界需要包含r
    '''
    l , r = 0, len(arr) - 1  
    while l <= r:            

        mid = (l+r)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1   # 明确区间的要求,只要使用过的,一律绕过。
        else:
            r = mid - 1   # 明确区间的要求,只要使用过的,一律绕过。
    return -1

```

**左闭右开,不包括End区间, end exclusive**
```
def binarySearch(arr, target):
    '''
    定义:在[l...r)的范围里寻找target, 因为这里定义是不需要将end归入范围区间
    exclusive,所以while循环的边界小于End即可,因为length本身长度会比index大1
    相对应的,每次target的value小于arr[mid]的时候,我们在重新定义新的end时候,
    也选择exclusive的模式,r = mid即可
    '''
    l , r = 0, len(arr)
    while l < r:            
        mid = l + (r-l)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1  
        else:
            r = mid
    return -1

```

#### 痛点2.5 :  死循环
上面的情况还只是把边界的其中一个写错, 也就是右边的边界值写错, 如果两者同时都写错的话, 可能会造成死循环, 比如下面的这个程序:

```
    l , r = 0, len(arr) - 1
    while l <= r:            
        mid = l + (r-l)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid
        else:
            r = mid
    return -1
```

这个程序采用的是左闭右闭的区间. 但是,
当 target < arr[mid] 的时候, 那么下一次查找的区间应该为 [mid + 1, right], 而这里变成了 [mid, right];  
当 target > arr[mid] 的时候, 那么下一次查找的区间应该为 [left, mid - 1], 而这里变成了 [left, mid]. 两个边界的选择都出现了问题, 因此, 有可能出现某次查找时始终在这两个范围中轮换, 造成了程序的死循环.

<br><br>

## Binary Search | 模板选择
@gengwuli 提出了模板一致性的观点,我也十分赞同。公瑾的策略是95%的情况下都用以下模板:
```
def binarySearch(arr, target):
    l , r = 0, len(arr) - 1  
    while l <= r:            
        mid = (l+r)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1
        else:
            r = mid - 1
    return -1
```

极个别情况会采用以下的模板:
```
def binary_search(array, target):
    start, end = 0, len(array) - 1
    while start + 1 < end:
        mid = (start + end) / 2
        if array[mid] == target:
            start = mid
        elif array[mid] < target:
            start = mid
        else:
            end = mid

    if array[start] == target:
        return start
    if array[end] == target:
        return end
    return -1
```

至于为什么不采用一个模板,是因为在大部分题的时候,运用第一种模板能够有更好的可读性
而第二个模板专门针对的是第一个模板的短板:当要access数组边界的数,如果边界的数在运行中出现更改,可能越界。虽然这种情况也可以用Edge Case来写,但太过麻烦。这点我们后面具体说来。

这里插一句话:**用的惯的模板**才是最适合你的,**切记**

<br><br>

## Binary Search | 题型

![快祝我好人一身平安]()

题目类型分为三类:
1. 有明确Target
2. 没有明确Target
3. 没有明确Target (可越界类型)

### 第一类题:有明确Target的题型

这一类题,会要求你找一个Target值,一般找到就返回Target值的下标或者Boolean函数。基础题目举两个例子:

#### Leetcode 374.  Guess Number Higher or Lower
> 告知Target是1到N之间的一个数,然后返回这个数的下标

```
class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        l , r = 0 , n
        while l <= r :
            mid = l + (r-l)//2
            toggle = guess(mid)
            if toggle == 0:
                return mid
            if toggle == 1:
                l = mid + 1
            else:
                r = mid - 1
```

#### Leetcode 367.  Valid Perfect Square

> 给定一个数值,判断是不是Perfect Square,这里只需要从0到Target中选择折中点,然后不停乘方和Target比对即可,因为返回是Boolean,同样不需要考虑边界
```

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        l, r = 0, num
        while l <= r:
            mid = l + (r-l)//2
            if mid ** 2 == num:
                return True
            if num > mid ** 2:
                l = mid + 1
            else:
                r = mid - 1
        return False
```

由于这一类题基本上就是套公式,直接考公式的几率很小。所以Medium以上的题目会对边界的选定模糊化,我们要做的是明确边界,然后再套公式。下面举例二分经典题:

#### 33. Search in Rotated Sorted Array

> 取中间值以后会发现,左边或者右边,至少有一边是sorted的,根据这个特性,搭配下面这个神图,就能理解下一段的代码


```
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return -1
        l , r = 0, len(nums) - 1

        while l <= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                return mid
            if nums[mid] >= nums[l]:
                if nums[l] <= target <= nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] <= target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1
```

![来自水中的鱼]()


<br><br><br><br>


### 第二类题:没有明确Target的题型

> 纳尼,你说你弄不懂到底返回`left`还是`right`,不慌,边界处理[神器](http://pythontutor.com/visualize.html#mode=display)镇楼。
该神器的使用方法:把代码拷过去,然后initiatize一个object,随便传入一个Test Case,然后点运行。代码会一步一步的跑,你就可以看你`left`和`right`在每一层迭代之后的值了。

这一类的题比较多变,可能会要你找
* 比Target大的最小值
* 比Target小的最大值
* 满足要求的第一个值
* 不满足要求的最后一个值
* ...

在刷这类题前,我们先看看模板,在迭代退出的时候,`left`和`right`的位置:

![]()

Case 1:
`Array = [1,2,3,5,6], Target = 4`

![](https://raw.githubusercontent.co ... g/binary_case1.jpeg)

首先这个程序肯定返回`-1`。我们的模板对While Loop定义如下:
`while l <= r:`
那么只有当`l > r`的时候,While Loop才会终止。
重点来了,当迭代结束后,假设`Target`为4, L和R的位置分别对应着两个条件:
`L`对应的是:第一个比4大的坐标, 根据这道题的定义就是比Target大的最小值
`R`对应的是:最后一个比4小的坐标,根据这道题的定义就是比Target小的最大值


Case 2:
`Array = [1,2,3,5,6], Target = 7`

根据我们While Loop的特性,有一个Edge的情况就是,L最大可以等于`len(array)`

![](https://raw.githubusercontent.co ... g/binary_case2.jpeg)

这里可以看到,如果我们要返回array[l],系统是会报错的,因为我们的L已经越界了,这个局限性是这套模板的小短板,当然,只要大家记住这一点,以后就可以写出相对应的Edge Case处理。

`l` 和 `r` 的位置和定义清楚了以后,我们来做做题。

<br><br><br>

#### 返回`l`的情况: 33. Search in Rotated Sorted Array

> 给了一个Target值,找到在Array里,Target按顺序应该插入的位置。

```
class Solution:
    def searchInsert(nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] == target:
                return mid
            if target > nums[mid]:
                l = mid + 1
            else:
                r = mid - 1
        return l
```

这里我们同样可以用镇楼法宝模拟下L,R在迭代结束后的下标

```
Input: [1,3,5,6], 2
Output: 1
```

`l`的下标是1, 定义是第一个满足条件的最小值。
`r`的下标是0,定义是最后一个不满足条件的最大值。

我们返回`l` 即可,另外还要说一点,这个模板对于这道题得天独厚的好处就是,不需要考虑当target插入的下标等于`len(arr)`的Edge Case,因为`l`本身就自带这个特性。


<br><br><br>



#### 返回`r`的情况:458. Last Position of Target (Lintcode)

> 给了一个Target值,找到在Array里,该Target值出现最后的坐标

```
class Solution:
    def lastPosition(self, nums, target):
        if not nums:
            return -1
        l , r = 0 , len(nums) - 1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid - 1
        if nums[r] == target:
            return r
        else:
            return -1
```

这道题的Array里面会有重复,去重的方式就是当`nums[mid] == target`的时候,对left进行增值。这样就可以去掉左边重复的数。

举例:

```
Input: [1, 2, 2, 4, 5, 5]
target = 2, return 2
```

`l`的下标是3, 定义是第一个不满足条件的值
`r`的下标是2,定义是最后一个满足条件的值。

所以返回`r`


<br><br><br>


#### 楼上两题的合体:34. Search for a Range

> 分别找到第一个位置,和最后一个位置,返回一个区间。

```
class Solution:
    def searchRange(self, nums, target):
        l = self.findLeft(nums, target)
        r = self.findRight(nums, target)
        return [l, r] if l <= r else [-1, -1]


    def findLeft(self, nums, target):
        l, mid, r = 0, 0, len(nums)-1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l   


    def findRight(self, nums, target):
        l, mid, r = 0, 0, len(nums)-1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid - 1
        return r
```




<br><br><br><br>

### 第三类题:没有明确Target的题型,可越界类型

这种类型的题目,用 `l <= r` 的模板可能会越界,我们可以填写个别的Edge Case处理,或者套用其他比如 `l < r` 或者 `l + 1 < r`的模板解决。


#### 162.  Find Peak Element

找峰值,mid比对的区间是 nums[mid + 1],这种情况当`l` 越界等于 `len(nums)`就会报错,所以可以选择用 `while l + 1 < r`的区间,最终对`l`和`r`进行比对。当然也可以写Edge处理。

```
class Solution:
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l , mid , r = 0, 0, len(nums) - 1
        while l + 1 < r:
            mid = l + (r-l)//2
            if nums[mid] < nums[mid + 1]:
                l = mid
            else:
                r = mid
        if nums[l] > nums[r]: return l
        else: return r
```

#### 153.  Find Minimum in Rotated Sorted Array

这道题最终要返回的`nums[l]`。同样,可以写Edge Case处理,也可以使用 `while l < r` 或者 `while l + 1 < r`来解。
```
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l, r = 0, len(nums) - 1
        while l + 1 < r:
            mid = l + (r - l) // 2
            if nums[mid] > nums[r]:
                l = mid
            else:
                r = mid
        return min(nums[l], nums[r])
```




参考:
1. [二分查找学习札记](http://www.cppblog.com/converse/archive/2009/10/05/97905.aspx) | 作者: 那谁
2. [Search in Rotated Sorted Array 配图](http://fisherlei.blogspot.com/20 ... d-sorted-array.html) | 作者: 水中的鱼


评分

参与人数 44大米 +136 收起 理由
anyonedy + 1 给你点个赞!
丑猪宝 + 2 很有用的信息!
CryingTiger + 1 很有用的信息!
blueones + 1 很有用的信息!
Yooohooo + 2 给你点个赞!
蛋蛋yx + 2 谢谢分享!
lemoncorn1123 + 1 很有用的信息!
LeoSun + 2 很有用的信息!
诺言哥要早起 + 1 给你点个赞!
SoMendokusaii + 1 赞一个

查看全部评分


上一篇:湾区线下刷题自习室招人啦
下一篇:Morris Traversal 的问题

本帖被以下淘专辑推荐:

  • · 刷题|主题: 55, 订阅: 13
我的人缘0

升级   25%

loonreg 2019-7-6 08:26:14 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
可以自己推一下,如果遵循下面的基本原则,就只需要一种写法。推导过程就省略了,建议大家举几个例子帮助理解,以免理解错误,毕竟自然语言是有歧义的。

基本原则就是:

1. 使用闭区间 [L, R] (用左闭右开区间也可以,只不过要相应地修改下面的几个原则)
2. 永远使用 while(L <= R)
3. 永远使用 L = mid + 1; R = mid - 1
4. 退出while循环之后,L和R一定满足 L = R + 1
5. return L 或者 return R

第5条需要自己现场稍微推一下,但是不难。基本规律是, 如果是按照下面的代码(假设数组 a 是单调递增序列)

[C++] 纯文本查看 复制代码
if(a[mid] < target)  L = mid + 1;
else   R = mid - 1;


那么,退出while循环之后,L 的位置一定在所有"<target" 的数的右边;R的位置一定在所有 "≥target" 的熟的左边。也就是说,a[R] <= target < a[L]

换言之,使得 L = mid  + 1 的 if 语句用了什么条件,在退出while循环之后,所有满足这个条件的数全都在 L 的左边;使得 R = mid - 1 的 if 语句用了什么条件,在退出while循环之后,所有满足这个条件的数全都在 R 的右边。并且 L = R + 1

所以,如果把上面的代码改成

[C++] 纯文本查看 复制代码
if(a[mid] <= target)  L = mid + 1;
else   R = mid - 1;


退出while循环之后,最后会得到,a[R] < target <= a[L],L = R + 1

如果知道这样的表达式,最后应该return L 还是 return R,就根据题目的具体要求来看了。

评分

参与人数 6大米 +8 收起 理由
xiehang019 + 3 很有用的信息!
lemoncorn1123 + 1 太给力了!
不知道小帅 + 1 赞一个
jc1992 + 1 很有用的信息!
yangmyfly + 1 完虐楼主
诺言哥要早起 + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   22.43%

jajaas 2018-12-10 08:23:21 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   94% (34)
 
 
5% (2)    👎
贴一个leetcode 的总结,我觉得这篇文章把二分总结得很好
https://leetcode.com/articles/introduction-to-binary-search/

里面把重点写出来了,我感觉主要是理解这三种模板的不同
1. start, end
2. loop condition, start <=end, start < end, start + 1 < end
3. move start or end, this is the key, if array have duplicate number, how to move?  这个如果不理解就很难应用好
4 process the left elements.

与大家共勉
回复

使用道具 举报

我的人缘0
sarahzjn 2018-7-5 15:24:52 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   87% (1009)
 
 
12% (146)    👎
楼主写的很棒,但是想提一个小小的理解上的误区,实际上任何有上下边界的搜索都大概率可以用binary search二分查找的含义是减半(排除错误的那一半)。类似例题有378
回复

使用道具 举报

我的人缘0

升级   36.29%

h379wang 2018-7-5 09:15:42 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (210)
 
 
5% (12)    👎
大赞楼主!!!收藏了!!!
回复

使用道具 举报

我的人缘1
肥宅快乐水 2018-7-5 12:39:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
100% (1)   👎
全局: 👍   85% (1077)
 
 
14% (186)    👎
写的挺好的, 中规中矩吧. 最重要的是要记住一个自己用的最舒服的代码.
回复

使用道具 举报

我的人缘0

升级   56.35%

groundzyy1 2018-7-5 13:49:58 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (1165)
 
 
2% (36)    👎
leetcode上那个分类总结其实就不错吧
回复

使用道具 举报

我的人缘0

升级   67.5%

Black-Tornado 2018-7-7 03:05:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (39)
 
 
0% (0)    👎
zhengyiyu 发表于 2018-7-5 13:49
leetcode上那个分类总结其实就不错吧

可以分享一下链接吗?谢谢
回复

使用道具 举报

我的人缘0

升级   67.5%

Black-Tornado 2018-7-7 03:06:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (39)
 
 
0% (0)    👎
楼主写的不错,但是感觉格式不是很好,最好写个md或者pdf,代码全乱了
回复

使用道具 举报

我的人缘0
 楼主| junior147147 2018-8-15 14:34:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (123)
 
 
4% (6)    👎
qianyilun 发表于 2018-7-7 03:06
楼主写的不错,但是感觉格式不是很好,最好写个md或者pdf,代码全乱了

原文是md格式的:https://github.com/yuzhoujr/leetcode/issues/8
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表