li星野头像
关注

二分查找六题通关：从标准模板到旋转数组（Python + C++）

二分查找六题通关：从标准模板到旋转数组（Python + C++）

二分查找是算法中最基础也最易错的技巧之一。本文整理了6道经典题目，每道题包含：题目描述、解题思路、图解（文本示意）、Python代码、C++代码、复杂度分析。掌握这些，二分查找类题目基本通关。

📌 题目清单

题号题目核心考点
704二分查找标准模板
35搜索插入位置二分边界
34在排序数组中查找元素的第一个和最后一个位置两次二分（左右边界）
33搜索旋转排序数组二分（判断有序部分）
153寻找旋转排序数组中的最小值二分（与右端点比较）
69x 的平方根二分 / 牛顿迭代

1. 二分查找（LeetCode 704）

题目描述

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

示例：
输入：nums = [-1,0,3,5,9,12], target = 9 → 输出：4
输入：nums = [-1,0,3,5,9,12], target = 2 → 输出：-1

解题思路

标准的二分查找模板：

  • 初始化左右指针 left = 0, right = len(nums)-1。
  • 当 left <= right 时循环：
    • 计算 mid = left + (right - left) // 2（防止溢出）。
    • 如果 nums[mid] == target，返回 mid。
    • 如果 nums[mid] < target，left = mid + 1。
    • 否则 right = mid - 1。
  • 循环结束返回 -1。

图解

nums = [-1,0,3,5,9,12], target=9
left=0, right=5, mid=2 -> nums[2]=3 < 9 → left=3
left=3, right=5, mid=4 -> nums[4]=9 == 9 → 返回4

Python代码

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

C++代码

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

复杂度分析

  • 时间复杂度：O(log n)。
  • 空间复杂度：O(1)。

2. 搜索插入位置（LeetCode 35）

题目描述

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

示例：
输入：nums = [1,3,5,6], target = 5 → 输出：2
输入：nums = [1,3,5,6], target = 2 → 输出：1
输入：nums = [1,3,5,6], target = 7 → 输出：4

解题思路

  • 二分查找，若找到目标直接返回下标。
  • 如果没找到，循环结束时的 left 就是插入位置（因为 left 指向第一个大于 target 的位置）。
  • 也可以统一用双闭区间模板，最后返回 left。

图解

nums = [1,3,5,6], target=2
left=0, right=3, mid=1 -> nums[1]=3 > 2 → right=0
left=0, right=0, mid=0 -> nums[0]=1 < 2 → left=1
left=1 > right 结束，返回 left=1

Python代码

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

C++代码

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

复杂度分析

  • 时间复杂度：O(log n)。
  • 空间复杂度：O(1)。

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

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果不存在，返回 [-1, -1]。

示例：
输入：nums = [5,7,7,8,8,10], target = 8 → 输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6 → 输出：[-1,-1]

解题思路

  • 写一个二分函数 findLeft 找左边界，findRight 找右边界。
  • 左边界：当 nums[mid] >= target 时移动右边界，最终 left 是第一个等于 target 的位置（若存在）。
  • 右边界：当 nums[mid] <= target 时移动左边界，最终 right 是最后一个等于 target 的位置。
  • 特殊处理：如果左边界越界或值不等于 target，返回 [-1,-1]。

图解

nums = [5,7,7,8,8,10], target=8
找左边界：
left=0,right=5,mid=2->7<8 → left=3
left=3,right=5,mid=4->8>=8 → right=3
left=3,right=3,mid=3->8>=8 → right=2
left=3 > right 结束，left=3
找右边界：
left=0,right=5,mid=2->7<=8 → left=3
left=3,right=5,mid=4->8<=8 → left=5
left=5,right=5,mid=5->10<=8? 否 → right=4
left=5 > right 结束，right=4
结果[3,4]

Python代码

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

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

    l = findLeft()
    r = findRight()
    if l <= r and l < len(nums) and nums[l] == target:
        return [l, r]
    return [-1, -1]

C++代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = findLeft(nums, target);
        int right = findRight(nums, target);
        if (left <= right && left < nums.size() && nums[left] == target) {
            return {left, right};
        }
        return {-1, -1};
    }

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

复杂度分析

  • 时间复杂度：O(log n)。
  • 空间复杂度：O(1)。

4. 搜索旋转排序数组（LeetCode 33）

题目描述

整数数组 nums 按升序排列，在某个未知点进行了旋转。给定 target，若存在返回下标，否则返回 -1。要求时间复杂度 O(log n)。

示例：
输入：nums = [4,5,6,7,0,1,2], target = 0 → 输出：4
输入：nums = [4,5,6,7,0,1,2], target = 3 → 输出：-1

解题思路

  • 在二分过程中，总能判断哪一半是有序的。
  • 如果 nums[left] <= nums[mid]，则左半有序：
    • 若 target 在左半范围内，则 right = mid - 1；否则 left = mid + 1。
  • 否则右半有序：
    • 若 target 在右半范围内，则 left = mid + 1；否则 right = mid - 1。

图解

nums = [4,5,6,7,0,1,2], target=0
left=0,right=6,mid=3 -> nums[3]=7, left有序[4,5,6,7], target=0不在其中 → left=4
left=4,right=6,mid=5 -> nums[5]=1, 右半有序[0,1,2], target=0在其中 → right=4
left=4,right=4,mid=4 -> nums[4]=0 → 返回4

Python代码

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        # 左半有序
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 右半有序
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

C++代码

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

复杂度分析

  • 时间复杂度：O(log n)。
  • 空间复杂度：O(1)。

5. 寻找旋转排序数组中的最小值（LeetCode 153）

题目描述

已知一个长度为 n 的升序数组在某个点旋转，找出数组中的最小元素。假设数组中不存在重复元素。

示例：
输入：nums = [3,4,5,1,2] → 输出：1
输入：nums = [4,5,6,7,0,1,2] → 输出：0

解题思路

  • 二分查找，每次与右端点比较。
  • 如果 nums[mid] > nums[right]，说明最小值在右半（mid 在左半较大区间），left = mid + 1。
  • 否则最小值在左半（包括 mid），right = mid。
  • 最后 nums[left] 即为最小值。

图解

nums = [3,4,5,1,2]
left=0,right=4,mid=2 -> nums[2]=5 > nums[4]=2 → left=3
left=3,right=4,mid=3 -> nums[3]=1 <= 2 → right=3
left=3,right=3 → 返回 nums[3]=1

Python代码

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

C++代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

复杂度分析

  • 时间复杂度：O(log n)。
  • 空间复杂度：O(1)。

6. x 的平方根（LeetCode 69）

题目描述

实现 int sqrt(int x) 函数，计算并返回 x 的平方根，其中 x 是非负整数。返回整数部分，小数部分舍去。

示例：
输入：4 → 输出：2
输入：8 → 输出：2（因为 2^2=4, 3^2=9 > 8）

解题思路

  • 二分查找范围 [0, x]。
  • 找满足 mid*mid <= x 的最大 mid。
  • 注意用 mid <= x // mid 避免溢出。
  • 也可用牛顿迭代法。

图解

x=8
left=0,right=8,mid=4 -> 4*4=16>8 → right=3
left=0,right=3,mid=1 -> 1<=8 → left=2
left=2,right=3,mid=2 -> 4<=8 → left=3
left=3,right=3,mid=3 -> 9>8 → right=2
left=3>right结束，返回right=2

Python代码（二分法）

def mySqrt(x):
    if x < 2:
        return x
    left, right = 0, x
    while left <= right:
        mid = left + (right - left) // 2
        if mid == x // mid:
            return mid
        elif mid < x // mid:
            left = mid + 1
        else:
            right = mid - 1
    return right

C++代码（二分法）

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;
        int left = 0, right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == x / mid) return mid;
            else if (mid < x / mid) left = mid + 1;
            else right = mid - 1;
        }
        return right;
    }
};

Python代码（牛顿迭代，可选）

def mySqrt(x):
    if x < 2:
        return x
    r = x
    while r > x // r:
        r = (r + x // r) // 2
    return r

复杂度分析

  • 时间复杂度：O(log x)（二分法）或 O(log x)（牛顿迭代，但常数更小）。
  • 空间复杂度：O(1)。

🎯 总结

题目核心技巧时间复杂度空间复杂度
704. 二分查找标准闭区间模板O(log n)O(1)
35. 搜索插入位置返回 left 即为插入位O(log n)O(1)
34. 查找首末位置两次二分找左右边界O(log n)O(1)
33. 搜索旋转数组判断有序半区O(log n)O(1)
153. 旋转数组最小值与右端点比较O(log n)O(1)
69. x的平方根二分查找整数部分O(log x)O(1)

二分查找的关键在于明确搜索区间和边界收缩条件。对于旋转数组，要善于利用“至少有一半是有序的”这一性质。多练习边界条件，写出 bug-free 的二分不难。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/qq_43441284/article/details/160899845

文章来源转载

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--