Featured image of post 数据结构与算法——二分查找
数据结构与算法 LeetCode

数据结构与算法——二分查找

介绍二分查找的原理，并且举例分析如何使用二分查找算法。

二分查找算法

  二分查找算法又称为折半查找(Binary Search)，是查找算法中简单、快速、高效的查找算法。使用要求是有序排列，且是顺序存储结构。

基本原理

  我们用文字梳理一下二分查找的原理，假设给定一个无重复值的递增数组[ ]int，变量名为nums ：

  1. 如果序列本身为空，不会进入二分查找算法。

  2. 如果序列不为空，从首尾开始进行二分，分为left、right、mid，mid就是首尾折半，判断条件为left <= right。

  3. 判断target和mid的值大小：

    • 如果此时nums[mid] == target，那么就找到了返回值，可以直接返回。
    • 如果此时nums[mid] > target，那么说明返回值应该在当前索引mid的左侧，此时end = mid - 1，查找范围缩短。
    • 如果此时nums[mid] < target，那么说明返回值应该在当前索引mid的右侧，此时start = mid + 1，查找范围缩短。

如果以代码来呈现的话就是这样。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

nums := []int{1, 2, 3, 4, 5, 6}
target := 5
left, right := 0, len(nums)-1
var output int
for left <= right {
	mid := (left + right) >> 1
	if nums[mid] == target {
		output = mid
		break
	} else if nums[mid] > target {
		right = mid - 1
	} else if nums[mid] < target {
		left = mid + 1
	}
}

  上面介绍的就是最基本的二分查找模板，不过有时候也有很多的其他的情况，二分并没有什么具体的模板写法，不要一味的去套模板，很容易出现超时、找错索引的情况，一定要理解好了去使用。

  但是这里面可能有人会有疑惑，为什么我看到其他人的写法在判断条件的for循环里是left < right？为什么有人的写法是left = mid，right = mid - 1或是left = mid + 1，right = mid？这些情况我们接着讨论。

其他情况

  我们修改一下原先的问题，带有重复数字的有序数组[]int，假设nums为{1,2,3,3,3,4}，如果我们按照上面的代码的话其实能找到3的位置，直接就能返回到第一个3的索引2为结果，但是如果我们想要找到最后一个3出现的位置该怎么办呢？这里面就存在了一个边界范围的情况讨论。这里我先以这道题为例，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

nums := []int{1, 2, 3, 3, 3, 4}
target := 3
left, right := 0, len(nums)-1
for left < right {
	mid := (left + right + 1) >> 1
	if nums[mid] > target {
		right = mid - 1
	} else {
		left = mid
	}
}

  这么一看是不是区别很大？但是却又和我们看到其他人写的二分法很像的样子。这样写比较好看，但同样也存在着问题，来分析和解释一下这段代码。

  • 首先注意到了为什么这里面是left < right而不是left <= right，因为这道例子我们想要找的是右边界，所以搜索范围希望是一个从左到右，(left,right]，左开右闭的区间，这个搜索区间是和我们定义的right有关，如果你的right定义成了len-1，那就说明我们的搜索区间是[left,right]，如果是len就是[left,right)，因为nums(len)会越界。而这里的left < right在最后left == right时，可以让程序从[left,right)中正常终止，否则会陷入死循环。不过这个其实和下面left与right的值更新一起决定的。
  • 接下来的mid := (left + right + 1) >> 1，这里的加1，是为了防止死锁，比如这道例子，假设我们的mid := (left + right) >> 1，在计算到left = 4，right = 5的时候，这是mid = 4，继续进入循环，进入循环后还是依然left = 4，right = 5，这样子就死锁了。
  • 最后是判断条件和更新值的不一样，这道例子是找右边界的target，有这三种情况：
    1. 在nums[mid] > target的情况，说明mid肯定不是我们要找的索引，目标值应该在mid的左边，right范围可以直接减1，即right = mid - 1；
    2. 在nums[mid] = target的情况，这时候没办法说明mid是最右边的，但可以肯定的是，至少是在mid靠右的部分，所以此时该更新left = mid，而不是left = mid + 1我们保留当前的mid还在我们接下来的搜索范围内，这样子避免万一当前mid就是右边界从而导致找不到值；
    3. 在nums[mid] < target的情况，说明mid肯定不是我们要找的索引，目标值应该在mid的右边，有人会疑惑，那不该是left = mid + 1吗？不这么写是因为有一种情况，[2,2]，如果我们想找target = 3，因为所有的值都比目标值小，我们返回的left就会越界超出索引，这种情况是在此写法下会发生的问题。

  另外大家思考一下，如果找的目标值不存在nums里我们返回的是什么呢？比如上面的代码中，如果我们的目标值是0的话，返回的是0，如果目标值是5的话，返回的是5。这里其实是返回小于目标值的最右边界索引。

  到这可能很多人也懵了，那这么多情况该怎么处理好呢，感觉写起来很困难。

思路

  最开始我也在这地方卡了很久，可能是会做了一道题，再出另一道题就不会做了，一道题的二分法写法肯定不只是一种，这个是根据left和right的定义，还有判断规则来决定的，这个需要多总结。我个人认为二分的思路需要如下，以一道题为例：

Leetcode 35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为$O(\log n)$的算法。

  • 首先我们先理清题意，这道题转换一下就是要找到目标值，返回其索引，如果不存在则找到大于目标值的最左边界，如果都小于目标值的话，那就返回len(nums)。
  • 理清楚了这道题的是要找左边界，那么我们就先来思考判断条件，如果我们的nums[i] > target的话，那么我们的target可能是在[0，i]之间，这里之所以i也包含是因为，如果不存在目标值的话，i可能是大于目标值的最左边界，所以要保留该索引，或者这么思考，如果我们的nums[i] < target，那么i下的值肯定不是我们要找的值，搜索空间应该在i之后，所以应该是[i+1, ]。
  • 在理清楚判断规则后，接下来就是left和right的定义了，这道题right定义成len(nums)-1，这个就像上面解析所说，是根据自己写法的定义，如果说是循环条件left <= right的话，那么我们的left和right都不能更新成mid，也就是left = mid + 1和right = mid - 1这种形式，因为防止进入死锁，没有办法终止，反之，如果left < right这样的条件，最后的结果就是left == right，可以终止循环。

  按照上面的思路我们写出来该题的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func searchInsert(nums []int, target int) int {
    if target > nums[len(nums)-1] {
        return len(nums)
    }
    left, right := 0, len(nums)-1
    for left < right {
        mid := (left + right)/2
        if nums[mid] < target {
            left = mid + 1
        }else {
            right = mid //这里的条件left < right可以防止死循环
        }
    }
    return left
}

  那如果循环条件是left <= right的代码应该是这样:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func searchInsert(nums []int, target int) int {
    if target > nums[len(nums)-1] {
        return len(nums)
    }

    left, right := 0, len(nums)-1
    for left <= right {
        mid := (left + right)/2
        if nums[mid] < target {
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
    return left 
}

  到这里，是否对二分法熟悉了很多，那么再来看一道例题:

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

  注：该题与 剑指Offer 53 - I. 在排序数组中查找数字Ⅰ 题干一样，只是返回要求不同。

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回[-1, -1]。 进阶：你可以设计并实现时间复杂度为$O(\log n)$的算法解决此问题吗？

  • 首先看这道题我们就清楚了是要找到目标值的最左和最右边界题，而且题干给了题意是$O(\log n)$的算法，这就说明要使用二分法来做了，这个要记住，不少题会这么说，这也是二分法的时间复杂度，很有标志性。
  • 然后我们首先要知道，如果数组的长度是0，或者目标值大于数组最大的值，或者小于数组最小的值，那么就可以直接返回要求的[-1. -1]。
  • 接下来就是两步二分法，分别找左右边界，第一个二分法找左边界，我们定义left和right分别是0和len(nums)-1，循环条件为left < right，找左边界的化，如果是nums[mid] < target，这种情况说明当前mid下的值肯定不是我们所要找的值，搜索范围应该[mid + 1, ]，所以left = mid + 1，或者思考，如果是nums[mid] >= target，在等于的情况下好说，可能是最左边界，但是要继续向左找，所以保留mid，在大于的情况下，一是因为循环条件的设定，另一个是因为为了找左边界，如果没有目标值的话，会返回大于目标值的最左边界，令right = mid。最后我们返回，start = left。
  • 那么接下来就是找右边界了，定义和循环条件还是不变，如果nums[mid] > target，这说明了当前值过大了，那么我们要找的范围就是从[0, mid - 1]，所以此时缩小范围，令right = mid - 1，反之，如果是nums[mid] <= target，在等于的情况下很好理解，该值可能是最右边界，所以保留继续向右搜索，如果是小于的情况下，考虑到如果没有目标值，则返回小于目标值的最右边界，所以此时令left = mid。最后我们返回end = left。
  • 最后就是如果真的没有目标值，那就是左边界的索引大于右边界的索引，即start > left。

  按照上面的思路我们写出来该题的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func searchRange(nums []int, target int) []int {
    if len(nums) == 0 || target > nums[len(nums)-1] || target < nums[0] {
        return []int{-1,-1}
    }
    start, end := 0, 0
    left, right := 0, len(nums)-1
    for left < right {
        mid := (left+right) >> 1
        if nums[mid] < target {
            left = mid + 1
        }else {
            right = mid
        }
    }
    start = left

    left, right = 0, len(nums)-1
    for left < right {
        mid := (left+right+1) >> 1
        if nums[mid] > target {
            right = mid - 1
        }else {
            left = mid
        }
    }
    end = left
    if start > end {
        return []int{-1, -1}
    }
    return []int{start, end}
}

  如果能理解到这，或者这两道题可以做出来了那至少正常的二分法是了解差不多了，接下来再举两道同类型的，我认为比较有代表性的二分法题：

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到[4,5,6,7,0,1,2] 若旋转 7 次，则可以得到[0,1,2,4,5,6,7] 注意，数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

  • 首先我们要思考的问题是，这道题为什么可以用二分法？二分法的要求不是有序吗？确实是这样我们来分析一下这道题，这道题相当于是两段有序的数组，且第二段的末尾接着第一段的首。我们可以思考一下情况：
    1. 如果是没有进行旋转，那么可以正常使用二分，此时nums[mid] > nums[left]，且nums[mid] < nums[right]，即正常的顺序，这样最小值一定在mid的左边范围
    2. 如果是nums[mid] < nums[left]，且nums[mid] < nums[right]，即中间值小于两边值，这说明肯定旋转过，最小值一定在包含mid的左边范围。
    3. 如果是nums[mid] > nums[left]，且nums[mid] > nums[right]，即中间值大于两边值，这也说明肯定旋转过，最小值一定在mid的右边范围。
    4. 最后一种情况是nums[mid] < nums[left]，且nums[mid] > nums[right]，这种情况不会发生。
  • 经过上面的分析我们可以看出来，通过比较nums[mid]与nums[right]的大小就能找出来接下来的搜索范围。所以这道题二分法是可行的。

  按照上面的思路我们写出来该题的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func findMin(nums []int) int {
    left, right, mid := 0, len(nums)-1, 0
    for left < right {
        mid = (left + right) >> 1
        if nums[mid] > nums[right] {
            left = mid + 1
        }else {
            right = mid
        }
    }
    return nums[left]
}

Leetcode 154. 寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

  • 理清了上面的那道题我们就对这道题的思路很清晰了，比较nums[mid]与nums[right]的值就可以，但是这道题为什么会成为困难题？因为这里包含了重复元素，如果是重复元素的话，我们上面的解法就会出现错误。但是真的不可以那么做了吗？
  • 我们可以举一个非常简单的例子看一下区别，上面的例子，是因为我们可以通过比较nums[mid]与nums[right]的值，可以判断该往哪个方向收缩搜索范围，而这道题，如果是[1,0,1,1]和[1,1,0,1]，唯独在nums[mid] == nums[right]的情况下，我们没有办法判断该往哪个方向收缩。所以这道题需要做的就是在相等的情况下如何去处理。这里的处理方式是在nums[mid] == nums[right]的情况下，令right = right - 1。正常来理解就是直到把这个重复的数字删去让nums[mid]与nums[right]的判断不受到影响就可以。
  • 那么条件是否允许呢？有两种情况，nums[right]是我们要找的最小值，且如果不是唯一的话，nums[mid]会依然在我们的搜索范围内，如果是唯一的话，那么此时nums[mid] == nums[right]，可以推出mid == right，但是因为是向下取整的，mid可能等于left不会等于right。

  按照上面的思路我们写出来该题的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func findMin(nums []int) int {
    left, mid, right := 0, 0, len(nums)-1
    for left < right {
        mid = (left + right) >> 1
        if nums[mid] > nums[right] {
            left = mid + 1
        }else if nums[mid] < nums[right] {
            right = mid
        }else if nums[mid] == nums[right] {
            right -- 
        }
    }
    return nums[left]
}

  二分算法的解析和例题题解就到这，如果这几道题能理解清楚的话，二分法基本没啥问题，不过还是要多加练习，刷刷LeetCode上面的题。

  这篇文章的结尾附上本人LeetCode主页： https://leetcode-cn.com/u/zonzeeli0523/

算法 go
Licensed under CC BY-NC-SA 4.0
comments powered by Disqus
© 2020 - 2023 Zonzee Li 👨‍💻
Built with Hugo
Theme Stack designed by Jimmy