二分查找不理解？一篇弄懂！--基础二分查找算法详细解释(带简单例题的详细解法)

时间：2025-02-19 08:28:10

本文参考:

灵茶山艾府

分享丨【题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小） - 力扣（LeetCode）

二分查找 红蓝染色法_哔哩哔哩_bilibili

本文主要详细讲解基础的二分算法中的查找，包括原理和模板，并用leetcode和洛谷的一些例题来进行实际题目讲解，如果觉得有帮助或者写的不错可以点个赞

目录

二分查找算法介绍

什么是二分查找？

那二分查找步骤是什么呢？

二分查找的代码怎么写呢？

代码编写思路：

闭区间写法:

左闭右开写法:

开区间写法:

库函数用法：

Python:

C++:

关于二分查找算法时间复杂度的简单证明:

例题一：

题目大意解析和思路:

代码(Python):

代码(C++):

库函数写法(Python):

库函数写法(C++):

例题二：

题目大意解析和思路:

代码(C++)

二分查找算法介绍

什么是二分查找？

我觉得洛谷那个例子举的很好

在一本英语词典中翻找一个单词的时候，可以从前往后一面一面的翻找，这就是顺序查找

但是英语词典里面的单词是按照字典序排的，那么可以先翻到词典的页数中间位置，然后根据要查找的单词再从前或者往后翻

这种思想就是二分查找

注意，二分查找一般只适用于有序的数组

那二分查找步骤是什么呢？

基本步骤如下:

  1. 确定初始范围：将搜索范围设置，比如整个数组。
  2. 计算中间位置：找到当前搜索范围的中间位置。
  3. 比较与缩小范围：
    • 如果中间位置的值是目标值，返回该位置。
    • 如果目标值小于中间位置的值，缩小范围到左半部分。
    • 如果目标值大于中间位置的值，缩小范围到右半部分。
  4. 重复步骤2和3，直到找到目标值，或者搜索范围为空（未找到目标值）
  5. 核心思想：每次迭代将搜索范围缩小一半

二分查找的代码怎么写呢？

代码编写思路：

根据二分查找的步骤，我们可以得出实际代码的大致的编写方法:

  1. 初始化：

    • 定义两个指针，left 和 right

  2. 迭代搜索：

    • 在 left 小于等于 right 的情况下，重复以下步骤：
      1. 计算中间位置 mid：mid
      2. 比较目标值 target 与 arr[mid] 的大小：
        • 如果 target 等于 arr[mid]，则找到了目标值
        • 如果 target 小于 arr[mid]，则目标值在左半部分，更新 right 
        • 如果 target 大于 arr[mid]，则目标值在右半部分，更新 left 

  3. 结束条件：

    • 如果在迭代过程中找到了目标值，返回目标值所在的位置。
    • 如果 left 超过 right 而没有找到目标值，说明目标值不在数组中，返回 -1 表示未找到

刚学习的可以根据上面的步骤尝试写一遍

根据上面步骤，我们可以写出以下代码(Python)（有详细注释）:

闭区间写法:

def binary_search(arr: List[int], target: int) -> int:
    '''
    在有序数组中查找目标值的索引。
    如果目标值存在，返回其索引；否则返回 -1。
    
    参数：
    arr (List[int]): 一个有序的整数数组。
    target (int): 需要查找的目标值。
    
    返回值：
    int: 目标值的索引，如果不存在则返回 -1。
    '''
    
    # 初始化搜索范围的左右边界
    left, right = 0, len(arr) - 1
    
    # 当左边界不超过右边界时，继续搜索
    while left <= right:
        # 计算中间位置
        mid = left + (right - left) // 2
        
        # 如果中间值等于目标值，返回中间位置
        if arr[mid] == target:
            return mid
        # 如果中间值小于目标值，说明目标值在右半部分，调整左边界
        elif arr[mid] < target:
            left = mid + 1
        # 如果中间值大于目标值，说明目标值在左半部分，调整右边界
        else:
            right = mid - 1
    
    # 如果循环结束后仍未找到目标值，返回 -1
    return -1

需要注意一点，在python中整数是”无限范围的“，可以比较无脑，可以直接写“mid = （right + left）// 2”但是其他语言中，整数相加可能会存在溢出的情况，也就是常说的”爆int“, 所以在计算中间位置的时候，建议这么编写：

mid = left + (right - left) // 2，先减后加

上述代码是闭区间写法，对于这种写法，为什么运行条件是left <= right? 为什么更新边界的时候是变成mid + 1或mid - 1？

现在用实际例子来进行理解这种写法的边界问题：

比如arr = [1, 3, 5, 7, 9, 11, 13, 15, 16],target = 7

开始的时候：l = 0, r = 8,那么mid = l + (r - l) // 2 = 4

此时arr[mid] = 9 > target = 7

缩小r = mid - 1 = 3

l = 0, r = 3

那么mid = l + (r - l) // 2 =  1

此时arr[mid] = 3 < target = 7

增大l = mid + 1 = 2

l = 2, r = 3

那么mid = l + (r - l) // 2 = 2

此时arr[mid] = 5 < target = 7

增大l = mid + 1 = 3

l = 3, r = 3

那么mid = 3,arr[mid] = target 返回mid

通过实际例子模拟可以看到，可能会存在left == right 的情况，循环条件就得这么写left <= right

其他写法:

左闭右开写法:

#左闭右开写法
def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1

开区间写法:

#开区间写法
def binary_search(arr: List[int], target: int) -> int:
    left, right = -1, len(nums)
    while left + 1 < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid
        else:
            right = mid
    return -1

这两种写法我就不举例子了，可以自己对着例子模拟一遍就可以理解了，写题目的时候用一种自己习惯的就行

库函数用法：

Python:

bisect_left(a, x, lo=0, hi=len(a))：在有序序列a中查找元素x应该插入的位置，并返回插入位置的索引。如果有多个相同元素，插入在其左侧。
bisect_right(a, x, lo=0, hi=len(a))：在有序序列a中查找元素x应该插入的位置，并返回插入位置的索引。如果有多个相同元素，插入在其右侧。

  • lo：指定搜索的起始位置。默认值为0，即从序列的开始处开始搜索。
  • hi：指定搜索的结束位置（不包含）。默认值为序列的长度len(a)，即搜索到序列的末尾。
C++:
  • lower_bound(first, last, val) 函数在有序范围 [first, last) 中查找第一个不小于 val 的元素的迭代器。
  • upper_bound(first, last, val) 函数在有序范围 [first, last) 中查找第一个大于 val 的元素的迭代器。
  • 这两个函数都返回一个迭代器,指向满足条件的元素。如果没有找到满足条件的元素,它们会返回 last 迭代器
  • 题目一般求解的是下标，则可以用数组开始的迭代器 () 进行减法运算，迭代器之间的减法运算会得到两个迭代器之间的距离,即元素的索引位置。

关于二分查找算法时间复杂度的简单证明:

在二分查找中，每次比较都会将搜索范围减半，这使得算法的时间复杂度是对数级别的。具体来说，假设有 n 个元素，每次比较都将搜索范围减半，即 n -> n/2 -> n/4 -> ... -> 1。在最坏情况下，需要进行 k 次比较才能找到目标元素或确定其不存在，其中 k 为满足 2^k <= n 的最大整数。因此，可以得出 k = log₂n。

综上所述，由于每次比较都将搜索范围减半，最多进行 log₂n 次比较就可以找到目标元素或确定其不存在。因此，二分查找的时间复杂度是 O(log n)。

例题一：

题目链接:

35. 搜索插入位置 - 力扣（LeetCode）

题目大意解析和思路:

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

题目的意思可以理解成在数组中找出第一个大于或等于target元素的下标，比如示例1

当target大于数组最大值的时候，返回数组长度即可，比如示例3

题目又要求时间复杂度是O(logn)那么就是二分算法，那具体怎么做呢

仔细理解二分查找模板代码

当left <= right的时候，查找的区间不断缩小，当left > right的时候，退出循环

此时left的下标对于的值刚好是大于或者等于target的元素

正好是这题所求的条件，那么可以直接写代码了

代码(Python):

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if 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 = () - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

库函数写法(Python):

根据上面我写的库函数

bisect_left(a, x, lo=0, hi=len(a))：在有序序列a中查找元素x应该插入的位置，并返回插入位置的索引。如果有多个相同元素，插入在其左侧。

这题可以直接使用这个，由于力扣中已经导入相关的类了，那可以直接写

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect_left(nums, target)

库函数写法(C++):

同理，参考我刚刚写的库函数

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return ranges::lower_bound((), (), target) - ();
    }
};

例题二：

P2249 【深基13.例1】查找 - 洛谷 | 计算机科学教育新生态 ()

题目大意解析和思路:

输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1​,a2​,…,an​，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。

输入格式

第一行 2 个整数 n 和 m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式

输出一行，mm 个整数，以空格隔开，表示答案。

输入输出样例

输入

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出

1 2 -1

题目的意思就是找出下面一行每个数字在上面数组中的位置，从1开始编号（这个好恶心）

这个数据量用循序查找肯定是不行的，所以需要用二分

这个里面会出现相同的数字，需要输出数字在序列中第一次出现的编号，我的思路是：

在二分查找的过程中，找到a[mid] == target的时候

由于是找最小的那个位置，此时可以先让res = mid

然后缩小r = mid - 1,再在[l , r]这个区间内找是否有a[mid] == target的情况

最后的答案即为最小的位置

代码(C++):

(最近看jiangly大佬的代码是写std::的，我这样的习惯还是挺好的，试试这样写)

long long binary_search(std::vector<long long>& a, int target) {
    int l = 0, r = () - 1, res = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == target) {
            res = mid;
            r = mid - 1;
        } else if (a[mid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::(0);
    int m, n;
    std::cin >> n >> m;
    std::vector<long long> a1(n);
    std::vector<int> a2(m);
    for (int i = 0; i < n; i++) {
        std::cin >> a1[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> a2[i];
    }
    std::vector<int> res(m);
    for (int i = 0; i < m; i++) {
        res[i] = binary_search(a1,a2[i]);
        if (res[i] != -1) {
            res[i]++;
        }
    }
    for (int i = 0; i < m; i++) {
        std::cout << res[i] << " ";
    }
    std::cout << "\n";
    return 0;
}

        我之后也会陆续更新一些比较高质量的基础算法详细解释，和一些解算法题的小技巧

        如果感兴趣，可以看看我之前写的文章:

        定长滑动窗口算法详细解释(带例题的详细解法)-****博客

        不定长滑动窗口算法详细解释(带例题的详细解法)-****博客

        算法题练习小技巧之区间合并--套路详细讲解带例题和源码(Python,C++)-****博客

相关文章