引言

在基础查询算法中有一个是不能避开的点：二分查找。

接触算法的同学翻开书的前几节，大概率是桶排序、冒泡、快排、然后就是经典的二分查找。

一开始接触的话不容易从理论中联系到生产实际上，查找，这个最基本的事情，怎么和项目级，产品级、工业级的实际使用构建联系起来呢？
这个问题是我们在展开二分法查找前要说明的问题，我们首先要达成的共识是要对它产生足够的兴趣。

什么是查找

查找，是将储备在需要时提取并使用的一个过程。任何事情，只要你想要通过某种行为达到目的，那么这种行为就一定包含查找的过程。

所以二分查找就可以认为是为了更快达到目的使用的一种手段。接下来让我们说说什么是二分。

什么是二分

所谓二分，就是指将线性的处理路线，变化为跳跃的。也因此他多了一些前置条件，来保证跳跃的过程不会忽视路过的风景。 —— 有序。

因为有序，我们就可以进行逻辑推理，不会受到混沌随机的因素干扰，所以让我们开始二分查找的探讨吧。。

思想核心是什么

首先让我们站在起点，这是一切的开始。
接着我们向前跳跃，落地之后看看脚下的内容和我的目标有多大的差距。

如果距离我们的目标要大，说明目标在我们后方（跳过了），接下来我们往回跳。
如果距离我们的目标要小，说明目标在我们前方（还没到），接下来我们再前跳。
我们并不关心在跳跃的过程中飞过了哪些东西，我们只要知道目标在哪，我们离它有多远。

这就是二分查找的思想，接下来解释：为什么他是闪电

为什么他会这么快

如果从逻辑上解答，在有序中我们可以通过推理跳过最为漫长的认知部分。
如果从行为上解答，他找的数要少的多。（这是有序给他的基础支撑）。

举个例子

如果我想要从十亿个数中找到目标，单次查找要一毫秒，那我线性查找可是要以年做单位的，（有兴趣的朋友可以算算具体的数据）。如果我使用二分查找的话，我实际的次数是30次。不到一秒钟。

这个例子有意义吗？其实，这是美国NASA在航天器登录前的两秒内要解决的事情。那十亿个数是他的登陆参数。

到此，我们知道了二分法查找的意义和思想。接下来，我们要回到实际中了。

代码实现

这里我使用了两种方式，感兴趣的同学可以用更多的方式自己尝试。

C++



/*
 * @Author       : Zry && 978524088@qq.com
 * @Date         : 2023-05-31 09:15:18
 * @LastEditors  : Zry && 978524088@qq.com
 * @LastEditTime : 2023-05-31 09:36:44
 * @FilePath     : /zryTest/test/C++/二分法查找/binarySearch.cxx
 * @Description  :
 *
 * Copyright (c) 2023 by 978524088@qq.com, All Rights Reserved.
 */

#include 
#include 

using namespace std;

#define int_t int
#define ZRY_OK 0
#define ZRY_NO_FIND -1

int_t binarySearch(int *List, const int iLen, const int item)
{
    int ilow = 0;
    int ihght = iLen - 1;
    int imin = 0;
    for (int i = 0; ilow  ihght; i++)
    {
        imin = (ilow + ihght) / 2;
        int iguess = List[imin];
        if (iguess == item)
        {
            return imin;
        }
        if (iguess > item)
        {
            ihght = imin - 1;
        }
        else
        {
            ilow = imin + 1;
        }
        printf("第 %d 查找 low=%d hight=%dn", i, ilow, ihght);
    }
    return ZRY_NO_FIND;
}
void test_binarySearch()
{
    int list[] = {1, 2, 3, 4, 5, 65, 66, 67, 68, 69, 77, 78, 79, 80, 100};
    printf("开始测试1n");
    assert(ZRY_NO_FIND != binarySearch(list, sizeof(list) / sizeof(int), 77));
    printf("开始测试2n");
    assert(ZRY_NO_FIND == binarySearch(list, sizeof(list) / sizeof(int), 55));
    printf("测试结束n");
}

int main()
{
    test_binarySearch();
    return ZRY_OK;
}

Python

def binarySearch(List, item):
    iLen = len(List)
    ilow = 0
    ihght = iLen - 1
    imin = 0
    i = 0
    while ilow  ihght:
        imin = (ilow + ihght) // 2
        iguess = List[imin]
        if iguess == item:
            return imin
        if iguess > item:
            ihght = imin - 1
        else:
            ilow = imin + 1
        print("第 %d 查找 low=%d hight=%d" % (i, ilow, ihght))
        i += 1
    return -1

def test_binarySearch():
    list = [1, 2, 3, 4, 5, 65, 66, 67, 68, 69, 77, 78, 79, 80, 100]
    print("开始测试1")
    assert(binarySearch(list, 77) != -1)
    print("开始测试2")
    assert(binarySearch(list, 55) == -1)
    print("测试结束")

if __name__ == '__main__':
    test_binarySearch()

总结

我们可以进一步的扩大二分的场景，从参数查找、到并发请求响应，从信息索引到数据支撑。

脱去外壳，只要我们可以在有序中找寻我们的目标，就可以二分。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 问鼎CodeXGLUE榜单，华为云UniXcoder-VESO-v1算法取得突破

摘要：华为云PaaS技术创新团队基于UniXcoder模型，在公开测试数据集（CodeXGLUE）上的代码搜索任务评测结果上取得突破，在CodeXGLUE榜单上排名中第一。本文分享自华为云社区《代码语义搜索算法哪家强？华为云UniXcoder-VESO-v1…

算法怎么算：二分为什么是闪电？引言什么是查找什么是二分思想核心是什么为什么他会这么快代码实现总结

引言