引言

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

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

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

什么是查找

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

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

什么是二分

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

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

思想核心是什么

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

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

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

为什么他会这么快

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

举个例子

如果我想要从十亿个数中找到目标，单次查找要一毫秒，那我线性查找可是要以年做单位的，（有兴趣的朋友可以算算具体的数据）。如果我使用二分查找的话，我实际的次数是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 <iostream>
#include <assert.h>using namespace std;#define int_t int
#define ZRY_OK 0
#define ZRY_NO_FIND -1int_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=%d\n", 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("开始测试1\n");assert(ZRY_NO_FIND != binarySearch(list, sizeof(list) / sizeof(int), 77));printf("开始测试2\n");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 = 0ihght = iLen - 1imin = 0i = 0while ilow <= ihght:imin = (ilow + ihght) // 2iguess = List[imin]if iguess == item:return iminif iguess > item:ihght = imin - 1else:ilow = imin + 1print("第 %d 查找 low=%d hight=%d" % (i, ilow, ihght))i += 1return -1def 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()