🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。

🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。

🏆🎉欢迎 👍点赞✍评论⭐收藏

🚀前言

在编程语言中，查找算法是指在一个数据集合中查找某个元素是否存在的算法。常见的查找算法包括：

1. 顺序查找（Sequential Search）：逐个遍历数据集来查找目标元素，时间复杂度为O(n)。
2. 二分查找（Binary Search）：在有序数据集合中，从中间位置作为起点不断划分区间并查找，时间复杂度为O(log n)。
3. 插值查找（Interpolation Search）：在有序数据集合中，根据目标元素与数据集合首尾之间的差值，利用插值估算目标元素的位置，时间复杂度为O(log log n)或O(n)。
4. 斐波那契查找（Fibonacci Search）：在有序数据集合中，根据斐波那契数列调整中间点的位置来查找，时间复杂度为O(log n)。
5. B树查找（B-Tree Search）：在平衡的B树中查找元素，时间复杂度为O(log n)。
6. 哈希查找（Hash Search）：通过哈希函数将元素映射到哈希表中，并在哈希表中查找元素，时间复杂度为O(1)。
7. 分块查找（Block Search）：将数据集合划分为若干块，在每个块中进行二分查找或顺序查找，时间复杂度为O(sqrt(n))。

以上算法都有各自适用的场景，开发者需要根据数据集合的特性和需求选择最适合的算法来进行查找。

🚀一、二分查找

🔎1.基本思想

二分查找算法是一种基于分治策略的搜索算法，也称为二分法。其基本思想是将要查找的数据与中间位置的数据进行比较，如果大于中间位置的数据，则在右半部分继续查找；如果小于中间位置的数据，则在左半部分继续查找；如果等于中间位置的数据，则直接返回。

具体的实现过程如下：

1. 首先确定整个查找区间的左右端点，定义为l和r；
2. 计算区间中间位置的下标mid，即mid=(l+r)/2；
3. 将要查找的数据与mid位置的数据进行比较，如果相等，则直接返回mid位置；否则，根据比较结果在左半部分或右半部分继续查找；
4. 如果未找到，则将区间缩小一半，即重新计算l和r的值，重复以上过程直到找到该数据或区间为空。

二分查找算法的时间复杂度为O(log n)，比线性查找的时间复杂度O(n)要更优秀，适用于有序数据的查找场景。

🔎2.复杂度分析

二分查找算法的时间复杂度为 O(log n)。

这是因为在二分查找的过程中，每次都将待查找区间缩小一半，因此要进行 log n 次查找才能找到目标元素。

具体来说，假设待查找的区间大小为 n，每次查找都将区间大小减半，直到区间大小为 1。则需要进行的查找次数为 log n。

🔎3.应用场景

二分查找算法的应用场景包括：

1. 有序数组中查找某个元素：二分查找算法可以在有序数组中快速查找某个元素，比如在升序数组中查找一个特定的数字。
2. 数据库查询优化：在数据库查询中，如果一个表中的数据是有序的，可以使用二分查找算法来进行优化查询，比如在按照时间戳排序的日志表中查找某段时间的记录。
3. 游戏中的特定位置查找：在游戏开发中，搜索算法常用于查找特定地点或场景中的对象，比如在地图上查找某个特定城市。
4. 搜索某个值在数据中出现的次数：有序数组中，相同元素的数量可以通过二分查找来实现。
5. 求解函数极值：在一些数学问题中，例如最优化问题，可以使用二分查找来求解函数的极值。

二分查找算法适用于要查找有序数据的场景。

🔎4.示例

int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };

Console.WriteLine(BinarySearch(array, 80));
Console.WriteLine(BinarySearch_dg(array, 66, 0, array.Length - 1));

Console.ReadKey();

static int BinarySearch(int[] array, int key)
{
    //直接求解
    var min = 0;
    var max = array.Length - 1;
    var mid = 0;
    while (min <= max)
    {
        mid = (min + max) >> 1;
        if (array[mid] > key)
        {
            max = mid - 1;
        }
        else if (array[mid] < key)
        {
            min = mid + 1;
        }
        else if (array[mid] == key)
        {
            return mid;
        }
    }
    return -1;
}

static int BinarySearch_dg(int[] array, int key, int low, int high)
{
    //递归法
    if (low > high) return -1;
    var mid = (low + high) >> 1;
    if (array[mid] > key)
        return BinarySearch_dg(array, key, low, mid - 1);
    else if (array[mid] < key)
        return BinarySearch_dg(array, key, mid + 1, high);
    else
        return mid;
}

请注意以上递归实现为尾递归：尽量使用尾递归

在最坏的情况下，二分查找需要在最后一次才能查找到目标关键字，假设原问题规模为n，每次折半原问题，设在第k次时问题规模变为1，那么令 2^k=1 ，因为指数和对数互为逆运算，解得 k=log_{2}n ，即二分查找在最坏的情况下的时间复杂度为： O(logn) 。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！