引言
在基础查询算法中有一个是不能避开的点：二分查找。
接触算法的同学翻开书的前几节，大概率是桶排序、冒泡、快排、然后就是经典的二分查找。
一开始接触的话不容易从理论中联系到生产实际上，查找，这个最基本的事情，怎么和项目级，产品级、工业级的实际使用构建联系起来呢？
这个问题是我们在展开二分法查找前要说明的问题，我们首先要达成的共识是要对它产生足够的兴趣。
什么是查找
查找，是将储备在需要时提取并使用的一个过程。任何事情，只要你想要通过某种行为达到目的，那么这种行为就一定包含查找的过程。
所以二分查找就可以认为是为了更快达到目的使用的一种手段。接下来让我们说说什么是二分。
什么是二分
所谓二分，就是指将线性的处理路线，变化为跳跃的。也因此他多了一些前置条件，来保证跳跃的过程不会忽视路过的风景。 —— 有序。
因为有序，我们就可以进行逻辑推理，不会受到混沌随机的因素干扰，所以让我们开始二分查找的探讨吧。。
思想核心是什么
首先让我们站在起点，这是一切的开始。
接着我们向前跳跃，落地之后看看脚下的内容和我的目标有多大的差距。
如果距离我们的目标要大，说明目标在我们后方（跳过了），接下来我们往回跳。
如果距离我们的目标要小，说明目标在我们前方（还没到），接下来我们再前跳。
我们并不关心在跳跃的过程中飞过了哪些东西，我们只要知道目标在哪，我们离它有多远。
这就是二分查找的思想，接下来解释：为什么他是闪电
为什么他会这么快
如果从逻辑上解答，在有序中我们可以通过推理跳过最为漫长的认知部分。
如果从行为上解答，他找的数要少的多。（这是有序给他的基础支撑）。
举个例子
如果我想要从十亿个数中找到目标，单次查找要一毫秒，那我线性查找可是要以年做单位的，（有兴趣的朋友可以算算具体的数据）。如果我使用二分查找的话，我实际的次数是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 -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=%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 = 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()
总结
我们可以进一步的扩大二分的场景，从参数查找、到并发请求响应，从信息索引到数据支撑。
脱去外壳，只要我们可以在有序中找寻我们的目标，就可以二分。
