Binary Search 总结帖 (更新完)

[tech-cow]

Binary Search

所有题目

Leetcode

Day 1

• 852 Peak Index in a Mountain Array
• 349 Intersection of Two Arrays
• 167 Two Sum II - Input array is sorted
• 350 Intersection of Two Arrays II
• 744 Find Smallest Letter Greater Than Target

---

Day 2

• 35 Search Insert Position
• 278 First Bad Version
• 367 Valid Perfect Square
• 374 Guess Number Higher or Lower
• 441 Arranging Coins
• 69. Sqrt(x)

---

Day 3 - 6

• 658. Find K Closest Elements
• 162. Find Peak Element
• 153. Find Minimum in Rotated Sorted Array
• 74. Search a 2D Matrix
• 34. Search for a Range
• 240. Search a 2D Matrix II
• 33. Search in Rotated Sorted Array
• 81. Search in Rotated Sorted Array II

Lintcode

Day 3 - 5

• 458. Last Position of Target
• 585. Maximum Number in Mountain Sequence
• 447. Search in a Big Sorted Array
• 462. Total Occurrence of Target
• 459. Closest Number in Sorted Array

题目的分类总结：

刷题先后顺序：

• 有明确Target的Easy, Medium
• 没有明确Target的Easy，Medium
  • 纳尼，你说你弄不懂到底返回left还是right，不慌，送你边界处理神器
  • 该神器的使用方法：把代码拷过去，然后initiatize一个object，随便传入一个Test Case，然后点运行。代码会一步一步的跑，你就可以看你left和right在每一层迭代之后的值了。
• 没有明确Target的Easy，Medium (边界变种)

[tech-cow]

公瑾总结

本总结参考/复制/修改了很多综合帖的内容，全部参考文档会赋予文章底部。
作者：公瑾
转载请注明出处：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;

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

痛点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]. 两个边界的选择都出现了问题, 因此, 有可能出现某次查找时始终在这两个范围中轮换, 造成了程序的死循环.

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来写，但太过麻烦。这点我们后面具体说来。

这里插一句话：用的惯的模板才是最适合你的，切记

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

第二类题：没有明确Target的题型

纳尼，你说你弄不懂到底返回left还是right，不慌，边界处理神器镇楼。
该神器的使用方法：把代码拷过去，然后initiatize一个object，随便传入一个Test Case，然后点运行。代码会一步一步的跑，你就可以看你left和right在每一层迭代之后的值了。

这一类的题比较多变，可能会要你找

• 比Target大的最小值
• 比Target小的最大值
• 满足要求的第一个值
• 不满足要求的最后一个值
• ...

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

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

首先这个程序肯定返回-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)

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

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

返回l的情况： 35. Search Insert Position

给了一个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本身就自带这个特性。

另外放一个某章模板的解法

class Solution:
    def searchInsert(self, arr, target):
        if not arr or len(arr) == 0: return 0
        l , r = 0 , len(arr) - 1
        while l + 1 < r:
            mid = (l + r) // 2
            if arr[mid] == target: 
                return mid
            elif arr[mid] < target:
                l = mid
            else:
                r = mid
        # Post
        if arr[l] == target: return l     # [1] | 1
        if arr[r] == target: return r     # [1, 2] | 2
        if arr[l] > target: return l      # [1, 3, 5, 6] | 0
        if arr[l] < target < arr[r]:      # [1,2,4,5] | 3
            return l + 1
        if arr[r] < target:               # [3, 5] | 9
            return r + 1

返回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

楼上两题的合体：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

某章模板

class Solution:
    def searchRange(self, nums, target):
        if not nums or len(nums) == 0: return [-1, -1]
        first = self.get_first(nums, target)
        last = self.get_last(nums, target)
        return [first, last]
    
    
    def get_first(self, arr, target):
        l , r = 0 , len(arr) - 1
        while l + 1 < r:
            mid = (l + r) // 2
            if arr[mid] == target:
                r = mid
            elif arr[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        #post
        if arr[l] == target: return l
        if arr[r] == target: return r
        return -1
        
        
        
    def get_last(self, arr, target):
        l , r = 0 , len(arr) - 1
        while l + 1 < r:
            mid = (l + r) // 2
            if arr[mid] == target:
                l = mid
            elif arr[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        #post
        if arr[r] == target: return r
        if arr[l] == target: return l
        return -1

第三类题：没有明确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. 二分查找学习札记 | 作者: 那谁
2. Search in Rotated Sorted Array 配图 | 作者: 水中的鱼

[gengwuli]

愚见: 首先是关于左闭右闭，合左闭右开。楼主对每一种情况分析的都很细致，但是实际操作起来往往需要统一口径，持续使用一种稳定的算法。这样实战的时候就不会被各种情况所干扰。个人认为左闭右闭更加直接，因为这样考虑左边界右边界都是同样的思路(l = m + 1, r = m - 1)。
然后就是+1和-1的问题，到底是+1还是-1，除了跟判断条件有关，还跟mid的计算有关。 mid = l + (r - l) / 2. 这里(r - l) / 2可能会省略额外的0.5导致mid会偏向左边。 如果r和l足够大，这不是事。 但是如果l + 1 = r也就是二者相邻的时候，这是(r - l) / 2 = 1 / 2 = 0.5 导致mid=l。 所以起码要保证赋值中不能出现l = mid。 仔细分析852这道题可以理解。
最后就是判断条件，到底是l < r, l <= r, 还是l + 1 < r？ 如果是l < r跳出循环后l = r, 如果l <= r出来l + 1 = r， 如果l + 1 < r的话, 那么出来就是l + 1 = r. 前两种条件都会出现循环内l + 1 = r的情况，所以需要留意mid=l。 第三种情况(l + 1 = r) ，因为只剩下两个，所以我们只需要再做一次判断就可以了。

综上所述，总结除了模板。

def search(arr:Array[Int], target: Int): Int = {
  var (l, r) = (0, arr.length - 1)
  while (l + 1 < r) {
    val m = l + (r - l) / 2
    if (arr(m) == target) {
      return m
    }
    if (arr(m) < target) {
      l = m
    } else {
      r = m
    }
  }
  if (arr(l) == target) { return l }
  if (arr(r) == target) { return r }
  return -1
}

首先判断条件总是l + 1 < r， 不用担心mid = l 循环的情况。然后l = mid, r = mid, 不用担心+1-1的情况。
出来只需要多一次判断左边和右边位置的数就可以了。非常稳定。

最后我们可能需要考虑，如果有重复元素怎么办，重复元素找左右边界。
还有一些题目本身不像二分查找，但是怎么转化为二分问题。

[Duan-JM]

太帅了，谢谢大佬呀～

[cc776]

总结特别到位 👍

[xiedaxia1hao]

Thanks!

[ShangxuanWu]

赞！提出一个修正：第二个模板还能针对，x不在arr里的情况（比如LC658）。如果x不在arr里，第一个模板就不能用。

[l0latgithub]

LC658 如何用某章的模板解决哪？新手问题，见谅！

[shiywang]

总结的很好，很适合新手，下面是进阶帖: 写对二分查找不能靠模板，需要理解加练习 （附练习题，持续更新）

[BWJerry]

非常漂亮的總結，想詢問
痛点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],
当 target > arr[mid] 的时候, 那么下一次查找的区间应该为 [left, mid - 1],
這兩個文字說明的下一次查找的区间是否寫反了謝謝！