X Tutup
Skip to content

binary_search.md

Latest commit

 

History

History
838 lines (696 loc) · 29.4 KB

binary_search.md

File metadata and controls

838 lines (696 loc) · 29.4 KB

二分搜索

二分搜索模板

给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1

模板四点要素

  • 1、初始化：start=0、end=len-1
  • 2、循环退出条件：start + 1 < end
  • 3、比较中点和目标值：A[mid] ==、 <、> target
  • 4、判断最后两个元素是否符合：A[start]、A[end] ? target

时间复杂度 O(logn)，使用场景一般是有序数组的查找

典型示例

binary-search

给定一个  n  个元素有序的（升序）整型数组  nums 和一个目标值  target  ，写一个函数搜索  nums  中的 target，如果目标值存在返回下标，否则返回 -1。

C++版本

// 二分搜索最常用模板
int search(vector<int>& nums, int target) {
    if(nums.empty()) return -1;

    int left = 0, right = nums.size() - 1;
    //处理循环
    while(left + 1 < right){
        int middle = left + (right - left) / 2;
        if(nums[middle] == target) return middle;
        else if(nums[middle] < target) left = middle;  //比较middle跟target的值
        else right = middle;
    }
    
    //最后还剩下left right两个值，做单独判断
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;

    return -1;
}

python3版本

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left + 1 < right: 
            mid = left + (right - left) // 2
            if nums[mid] == target: return mid
            elif nums[mid] < target: left = mid
            else: right = mid

        if nums[left] == target: return left
        if nums[right] == target: return right
        return -1

大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可

另外二分查找还有一些其他模板如下图，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛

binary_search_template

所以用模板#3 就对了，详细的对比可以这边文章介绍：二分搜索模板

如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁

// 无重复元素搜索时，更方便
int search(vector<int>& nums, int target) {
    if(nums.empty()) return -1;
    int left = 0, right = nums.size() - 1;
    //处理循环
    while(left <= right){
        int middle = left + (right - left) / 2;
        if(nums[middle] == target) return middle;
        else if(nums[middle] < target) left = middle-1;  //比较middle跟target的值
        else right = middle+1;
    }

    // 如果找不到，start 是第一个大于target的索引
    // 如果在B+树结构里面二分搜索，可以return start
    // 这样可以继续向子节点搜索，如：node:=node.Children[start]
    return -1
}

常见题目

x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

Python版本

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        left, right = 1, x//2 + 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if mid * mid == x: return mid
            elif mid * mid < x: left = mid
            else: right = mid
        
        if left * left > x: return left - 1
        elif right * right <= x: return right
        else: return left

有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。 进阶：不要 使用任何内置的库函数，如  sqrt 。

思路：只要num大于4，其平方数肯定不会超过num//2，这样可以减少一次二分运算，提升速度.

Python版本

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num // 2 + 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if mid * mid == num: return True
            elif mid * mid < num: left = mid
            else:
                right = mid
        if left * left == num or right * right == num: return True
        else: return False

Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。

思路：使用快速幂思想，二分法解决，需要注意奇偶数的不同

Python版本

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0
        res = 1.0
        m = abs(n)
        while m > 0:
            if m % 2: res = res * x
            x = x * x
            m = m // 2
        
        if n < 0: return 1. / res
        return res

寻找比目标字母大的最小字母

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

  • 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'

Python版本

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        if letters[0] > target or target >= letters[-1]: return letters[0]
        left, right = 0, len(letters) - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if letters[mid] <= target: left = mid #尽量往左移动
            else: right = mid
        
        if letters[left] > target: return letters[left]
        return letters[right]

两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序。

Python版本

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1, nums2 = sorted(set(nums1)), sorted(set(nums2))
        if len(nums1) <= len(nums2): return inter(nums1, nums2)
        else: return inter(nums2, nums1)

def inter(nums1, nums2):
    res = list()
    for i, num in enumerate(nums1):
        if find(num, nums2): res.append(num)
    return res

def find(num, nums):
    left, right = 0, len(nums) - 1
    while left + 1 < right:
        mid = left + (right - left) // 2
        if nums[mid] == num: return True
        elif nums[mid] < num: left = mid
        else: right = mid
    if nums[left] != num and nums[right] != num: return False
    return True

两个数组的交集II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

// 思路：需要考虑找到的数量

Python版本

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1, nums2 = sorted(nums1), sorted(nums2)
        if len(nums1) <= len(nums2): return inter(nums1, nums2)
        else: return inter(nums2, nums1)


def inter(nums1, nums2):
    res = list()
    i = 0
    while i < len(nums1):
        num = nums1[i]
        cnt1 = 1
        while i+1 < len(nums1) and nums1[i+1] == num:
            cnt1 += 1
            i += 1
        cnt2 = findNum(num, nums2)
        res.extend([num] * min(cnt1, cnt2))
        i += 1
    return res

def findNum(num, nums):
    left = find(num, nums, find_left=True)
    if left == -1: return 0
    right = find(num, nums, find_left=False)
    return right - left + 1

def find(num, nums, find_left):
    left, right = 0, len(nums) - 1
    while left + 1 < right:
        mid = left + (right - left) // 2
        if nums[mid] < num: left = mid
        elif nums[mid] > num: right = mid
        else:
            if find_left: right = mid
            else: left = mid
    if nums[left] != num and nums[right] != num: return -1
    if find_left:
        if nums[left] == num: return left
        else: return right
    else:
        if nums[right] == num: return right
        else: return left

两数之和II-输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。

//思路: 两种解题思路，一是二分，第二种是双指针，肯定双指针耗时更优 Python版本一：二分查找

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        '''
        这里使用二分法来找; 也可以使用双指针法
        '''
        for i, num in enumerate(numbers):
            right = find(target - num, i + 1, len(numbers) - 1, numbers)
            if right != -1: return [i+1, right+1]
        return [-1, -1]
def find(num, lo, hi, nums):
    while lo + 1 < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] >= num: hi = mid
        else: lo = mid
    if nums[lo] == num: return lo
    elif nums[hi] == num: return hi
    else: return -1

Python版本二：双指针

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            if numbers[left] + numbers[right] == target: return [left + 1, right + 1]
            elif numbers[left] + numbers[right] > target: right = right - 1
            else: left = left + 1
        return [-1, -1]

猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。

如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

  • -1：我选出的数字比你猜的数字小 pick < num
  • 1：我选出的数字比你猜的数字大 pick > num
  • 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

Python版本

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left + 1 < right:
            mid = left + (right - left) // 2
            if guess(mid) == 0: return mid
            elif guess(mid) == -1: right = mid
            else: left = mid
        if guess(left) == 0: return left
        else: return right

search-for-range

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。 如果目标值不在数组中，则返回[-1, -1]

思路：核心点就是找第一个 target 的索引，和最后一个 target 的索引，所以用两次二分搜索分别找第一次和最后一次的位置

Python3版本

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0: return [-1, -1]

        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] < target: left = mid
            elif nums[mid] > target: right = mid
            else:
                left = mid
                right = mid
                while left > 0 and nums[left-1] == target: left = left - 1
                while right < len(nums) - 1 and nums[right+1] == target: right = right + 1
                return [left, right]
        if nums[left] == target:
            if nums[right] == target: return [left, right]
            else: return [left, left]
        else:
            if nums[right] == target: return [right, right]
            else: return [-1, -1]
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0: return [-1, -1]
        '''
        分解成找两次，找最左边一次，找最右边一次
        '''
        left = findTarget(nums, target, True)
        if left == -1: return [-1, -1]
        right = findTarget(nums, target, False)
        return [left, right]

def findTarget(nums, target, find_left):
    left, right = 0, len(nums) - 1
    while left + 1 < right:
        mid = left + (right - left) // 2
        if nums[mid] < target: left = mid
        elif nums[mid] > target: right = mid
        else:
            if find_left: right = mid
            else: left = mid
    
    if find_left:
        if nums[left] == target: return left
        elif nums[right] == target: return right
        else: return -1
    else:
        if nums[right] == target: return right
        elif nums[left] == target: return left
        else: return -1

C++版本

vector<int> searchRange(vector<int>& nums, int target) {
    if(nums.empty()) return {-1, -1};
    int low = findTarget(nums, target, true);
    if(low == -1) return {-1, -1};
    int high = findTarget(nums, target, false);
    return {low, high};
}

int findTarget(vector<int>& nums, int target, bool findLeft){
    int left = 0, right = nums.size() - 1;
    while(left + 1 < right){
        int middle = left + (right - left)/2;
        if(nums[middle] < target) left = middle;
        else if(nums[middle] > target) right = middle;
        else{
            if(findLeft) right = middle;
            else left = middle;
        }
    }

    if(findLeft) {
        if(nums[left] == target) return left;
        else if(nums[right] == target) return right;
        else return -1;
    }
    else{
        if(nums[right] == target) return right;
        else if(nums[left] == target) return left;
        else return -1;
    }

}

找到k个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

思路有好几种：

  1. 找到最小值，然后双指针
  2. 直接找k长度的子序列
  3. 删去最远的剩下的就是最近的长度为k的子数组

Python版本

### 方法一
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        if len(arr) == k: return arr
        left, right = 0, len(arr) - 1

        while left + 1 < right:
            mid = left + (right - left) // 2
            if arr[mid] >= x: right = mid
            else: left = mid
        
        res = list()
        while len(res) < k:
            if right >= len(arr) or (left >= 0 and abs(arr[left]-x) <= abs(arr[right]-x)):
                res.insert(0, arr[left])
                left = left - 1
            else:
                res.append(arr[right])
                right = right + 1
        return res
### 方法二
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        '''
        直接定位mid为左边界；
        查找mid+k的结果是否满足要求；
        不满足的话二分法左右调整mid.
        '''
        if len(arr) == k: return arr
        left, right = 0, len(arr) - k
        while left + 1 < right:
            mid = left + (right - left) // 2
            if x - arr[mid] <= arr[mid + k] - x:
                right = mid
            else:
                left = mid
        
        if abs(arr[left] - x) <= abs(arr[right + k - 1] - x): return arr[left: left + k]
        else: return arr[right: right + k]

search-insert-position

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

int searchInsert(vector<int>& nums, int target) {
    if(nums.empty()) return 0;
    int left = 0, right = nums.size() - 1;

    while(left + 1 < right){
        int middle = left + (right - left) / 2;
        if(nums[middle] == target) return middle;
        else if(nums[middle] < target) left = middle;
        else right = middle;
    }

    if(target <= nums[left]) return left;
    else if(target <= nums[right]) return right;
    else return right + 1;
}

search-a-2d-matrix

编写一个高效的算法来判断  m x n  矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

C++版本

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if(matrix.empty() || matrix[0].empty()) return false;
    int rows = matrix.size();
    int cols = matrix[0].size(); 
    
    int left = 0, right = rows * cols - 1;
    while(left + 1 < right){
        int mid = left + (right - left) / 2;
        int valM = matrix[mid/cols][mid%cols];
        if(target == valM) return true;
        else if(target < valM) right = mid;
        else left = mid;
    }

    if(matrix[left/cols][left%cols] == target || matrix[right/cols][right%cols] == target) return true;
    
    return false;
}

Python版本

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        left, right = 0, rows * cols - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            val = matrix[mid//cols][mid%cols]
            if  val == target: return True
            elif val < target: left = mid
            else: right = mid

        if matrix[left//cols][left%cols] == target or matrix[right//cols][right%cols] == target:
            return True
        else: return False

first-bad-version

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用  bool isBadVersion(version)  接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

Python3版本

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n

        while left + 1 < right:
            mid = left + (right - left) // 2
            if not isBadVersion(mid): left = mid
            else: right = mid
        
        if isBadVersion(left): return left
        else: return right

C++版本

int firstBadVersion(int n) {
    int left = 1, right = n;
    while(left + 1 < right){
        int mid = left + (right - left) / 2;
        if(isBadVersion(mid)) right = mid;
        else left = mid;
    }
    if(isBadVersion(left)) return left;
    return right;
}

find-minimum-in-rotated-sorted-array

假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 Python版本

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        if nums[left] <= nums[right]: return nums[left] # 说明还是升序排列

        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] >= nums[right]: left = mid
            else: right = mid

        return min(nums[left], nums[right])

版本二

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] < nums[-1]: return nums[0] ## 说明顺序没变
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[left]:
                left = mid
            else:
                right = mid
        
        return min(nums[left], nums[right])

C++版本

int findMin(vector<int>& nums) {
    if(nums.empty()) return 0;

    int left = 0, right = nums.size() - 1;
    if(nums[right] > nums[left]) return nums[left]; //说明没有旋转

    while(left + 1 < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] > nums[left]) left = mid;
        else right = mid;
    }

    return min(nums[left], nums[right]);
}

find-minimum-in-rotated-sorted-array-ii

假设按照升序排序的数组在预先未知的某个点上进行了旋转 ( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。 请找出其中最小的元素。(包含重复元素)

// 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理

Python版本

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] < nums[-1]: return nums[0]
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            while left < right and nums[left] == nums[left+1]: left = left + 1
            while left < right and nums[right] == nums[right-1]: right = right - 1
            mid = left + (right - left) // 2
            if nums[mid] >= nums[right]: left = mid
            else: right = mid
        
        return min(nums[left], nums[right])

C++版本

int findMin(vector<int>& nums) {
    if(nums.empty()) return 0;
    int left = 0, right = nums.size() - 1;
    if(nums[left] < nums[right]) return nums[left]; // 说明没旋转
    while(left + 1 < right){
        //去重
        while(left < right && nums[left + 1] == nums[left]) left++;
        while(left < right && nums[right - 1] == nums[right]) right--;
        int mid = left + (right - left) / 2;
        if(nums[mid] >= nums[left]) left = mid;
        else right = mid;
    }
    return min(nums[left], nums[right]);
}

search-in-rotated-sorted-array

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组  [0,1,2,4,5,6,7]  可能变为  [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回  -1 。 你可以假设数组中不存在重复的元素。

Python版本

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] == target: return mid
            if nums[mid] > nums[left]:
                if target >= nums[left] and target <= nums[mid]: right = mid
                else: left = mid 
            else:
                if target <= nums[right] and target >= nums[mid]: left = mid
                else: right = mid
            
        if nums[left] == target: return left
        elif nums[right] == target: return right
        else: return -1

C++版本

int search(vector<int>& nums, int target) {
    if(nums.empty()) return -1;
    int left = 0, right = nums.size() - 1;
    while(left + 1 < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return mid;
        if(nums[mid] > nums[left]){
            if(target >= nums[left] && target <= nums[mid]) right = mid;
            else left = mid;
        }
        else{
            if(target <= nums[right] && target >= nums[mid]) left = mid;
            else right = mid;
        }
    }

    if(nums[left] == target) return left;
    else if(nums[right] == target) return right;
    else return -1;

}

注意点

面试时，可以直接画图进行辅助说明，空讲很容易让大家都比较蒙圈

寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 思路：规定了算法复杂度，那就是二分匹配法

Python3版本

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid+1]: left = mid
            else: right = mid
        
        if nums[left] < nums[right]: return right
        else: return left

前面几道题说明了，二分匹配中，不一定直接对比mid和target, left和mid, mid本身, mid和相邻(mid+1)，都是能做compare的。

search-in-rotated-sorted-array-ii

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组  [0,0,1,2,2,5,6]  可能变为  [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回  true，否则返回  false。(包含重复元素)

bool search(vector<int>& nums, int target) {
    if(nums.empty()) return false;
    int left = 0, right = nums.size() - 1;
    while(left + 1 < right){
        while(left < right && nums[left+1] == nums[left]) left++;
        while(left < right && nums[right-1] == nums[right]) right--;
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return true;
        if(nums[mid] >= nums[left]){   //注意是等号
            if(target >= nums[left] && target <= nums[mid]) right = mid;
            else left = mid;
        }
        else{
            if(target >= nums[mid] && target <= nums[right]) left = mid;
            else right = mid;
        }
    }
    if(nums[left] == target || nums[right] == target) return true;
    else return false;
}

总结

二分搜索核心四点要素（必背&理解）

  • 1、初始化：start=0、end=len-1
  • 2、循环退出条件：start + 1 < end
  • 3、比较中点和目标值：A[mid] ==、 <、> target
    • target不一定是既定的数字，也可能是start/end/mid+1对应的值,灵活应用
  • 4、判断最后两个元素是否符合：A[start]、A[end] ? target

练习题
X Tutup