二分法，实际上就是数学里给查找数字加个“分家”的游戏。 你拿个数，比如 37，要么一个区间，比如从 1 到 100。你心里有个秘密目标，想看看这个数能不能在开头，能不能在中间，要么是不是结尾。你随意在中间切一刀，比如切成两半。 这时候你得对半猜：这数是在左半边吗？还是在右半边？ 要是猜对了，那就不用费脑子再左右切换了，直接往那边去，一步到位。

要是猜错了呢？那就把猜错的半截扔一边，只盯着剩下的一半持续猜。 这套操作，就是二分法。它不像贪心算法那样非要每件事都“当下最优”，它更像是在玩“猜数字”游戏，通过不断把范围缩小一半，直到最终只剩下一块，最终直接喊出那个数。 看个具体的例子。我要找 37。 第一刀，我从 1 到 100 中间切。100 的一半是 50。37 比 50 小，说明肯定在 1 到 50 这个区间。 我接着在 1 到 50 里再切。50 的一半是 25。37 比 25 大，说明肯定在 26 到 50 这个区间。 再切一次。26 到 50 的中间是 38。37 比 38 小，说明在 27 到 38 之间。 再切一次。27 到 38 的中间是 32.5。37 比 32.5 大，说明在 33 到 38 之间。 目前区间挺窄了，从 33 到 38，一共 6 个数。我在这中间再切。33 和 38 的中间是 66 不对，是 33 加 38 除以 2 等于 35.5。37 比 35.5 大，说明在 36 到 38 之间。 最终只剩一个数了，37。

哎，找到了。 这过程实际上挺荒诞的，但也挺有趣。想象你在家里找钥匙，门把是锁。门把上有“左旋”和“右旋”两个开关。你不用试图把门把分成“左半边”和“右半边”这种概念，你直接用手摸一下，要么是把门把分成两半，拿着右手去试左边的半截，拿着左手去试右边的半截。 要是哪道关是“左旋”的，你就直接去试左边的半截。

要是是“右旋”的，你就直接去试右边的半截。 这种方式的核心，就是“舍弃”。

这不是偷懒，这是用数学的逻辑去替代逻辑的重复。 再想想算法里的“空间复杂度”。二分法之故此快，是出于每次操作都只需求处理一半的数据，要么说，处理了一半的数据后，剩下的数据量直接减半。

要是不用二分法，反而是用线性搜索，你得再遍历一遍，要么再遍历一遍。 比如找数组里的最大值。 线性搜索：你得从头到尾，遍历 `i` 从 0 到 `n-1`。每经过一个数，都要比较一次。总共比较 `n` 次。 二分法（要是数组有序）：你得先判断是不是有序。

要是是，你取中间值 `mid`。

要是 `arr[mid]` 等于你找的目标，直接回 `mid`。

要是大于，说明目标在左边，范围缩到 `left` 到 `mid-1`。

要是小于，说明目标在右边，范围缩到 `mid+1` 到 `right`。 实际上你会发现，每一次缩窄，实际上你都是跳过了一半的数字。 比如数组是 `1, 2, 3, 4, 5`，目标是 `3`。 第一次，中间是 3。直接找到。 要是数组是 `1, 2, 3, 4, 5, 6, 7`，目标是 `3`。 第一次，中间是 `4`。3 比 4 小，说明在左边。范围变成 `1, 2, 3`。 第二次，中间是 `2`。3 比 2 大，说明在右边。范围变成 `3`。 第三次，直接找到。 看起来只跳了一两次，但实际上你省掉了大量的比较。 还有一种应用场景，是“折半查找”。

这实际上就是二分查找，但逻辑略微有点不一样。它不是去删半，而是去去掉数据本身的数据。 比如你要查“2023 年”这个年份。你查一个库，里面有 1990 到 2024 的所有年份。 你取中间那个年份，比如 2018 年。 要是库里有 2018 年，你就直接告诉你找到了。 要是库里没有，你得看看，2018 年是在 1990 到 2018 之间吗？还是 2018 到 2024 之间？ 要是是，那你直接拿 2018 到 2024 这一半去查。 你看，这个逻辑实际上和“删除一半数据”是一样的。你只是把数据本身扔进了一个集合里，最终只剩下一个集合。 这听起来离“删除一半数据”挺远，但本质上是一样的。 在计算机底层，大量操作都是基于“位”的。你右移一位，就是把数字右移一位。

这不仅是位运算，它也是“舍弃”的过程。你舍弃了最低位，剩下的就是原数的一半。

这种“舍弃”在二分法里无处不在。 比如你在做递归。你写一个函数，递归到底的时候，参数变成了 0 要么边界值。

这时候你就不能再持续“舍弃”数据了，务必暂停。 要是不用递归，而是用循环。循环的条件是 `low

你想拿 30 颗。 你不会拿一半的 50 颗和一半的 100 颗凑。 你不会数 50 颗里的 30 颗，再数剩下的。 你会直接数 100 颗里的 30 颗，出于 50 颗里的 30 颗已经拿完了。 你会扔掉 50 颗剩下的 20 颗，只拿 100 颗里的 30 颗。 这就是二分法的逻辑。扔掉一半无法利用的局部，只利用另外一半。 在写代码的时候，这种思想也贼关键。 比如你写一个循环。循环的条件是 `while len(list) > 0`。 你每次循环，都会扔掉列表的一半元素。 这听起来挺亏，出于元素被扔掉了，但工夫复杂度是 O(n)。 为啥二分法的工夫复杂度是 O(log n) 而线性搜索是 O(n)？ 出于二分法扔掉的元素，是“不可再分”的。 想象一个列表：`[1, 2, 3, 4, 5, 6, 7, 8]`。 第一次扔，扔掉 `1` 和 `2` 之间的那两个，剩下 `[3, 4, 5, 6, 7, 8]`。 第二次扔，扔掉 `3` 和 `4` 之间的那两个，剩下 `[5, 6, 7, 8]`。 你看，每次扔的，都是中间那个位置左右的两个元素。 你在扔，你在扔，你扔了 10 个元素。 但要是你用线性搜索，你得遍历 `1, 2, 3, 4, 5, 6, 7, 8` 每一个数。 你用了 8 次比较。 用二分法，你只需求 4 次比较。 出于每次比较，你实际上已经“扔掉”了一次比较本事。 这种“扔掉比较本事”的过程，就是二分法的核心。 在算法竞赛里，时常有题让你求一个序列的和。题目给的是 `n` 个数字。 线性做法：`sum = 0; for x in nums: sum += x`。 这是 O(n)。 二分做法：要是你能用线形插值法？不中。 可是，要是你能预处理。

比如你有一个前缀和数组。 `prefix[i]` 是前 `i` 个数的和。 那你直接算 `prefix[n]`。 这是 O(1)。 你看，这比二分法快，出于二分法是把数据分成了两半，而前缀和是直接查表。 可是，大量题没法直接查表。

比如题目说“第 n 项是多少”，但你只能给你前 n 项的和，不能给你前 n 项的列表。 这时候你就得用二分查找。 你拿一个 `n`，你要判断第 `n` 项是不是奇数。 你一次查一个数。 `mid = (left + right + 1) / 2`。 要是 `arr[mid]` 是奇数，说明第 `mid` 项可能是奇数，也可能是偶数，不能确定。 要是 `arr[mid]` 是偶数，说明第 `mid` 项一定是偶数。 什么的，这里逻辑有点绕。 让我们换个角度。 我们要找的是“第 `n` 项是奇数”这个命题是否为真。 线性法：遍历 `1` 到 `n`。 二分法：`low = 1, high = n`. `mid = (low + high) / 2`. 要是 `arr[mid]` 是奇数，说明 `mid` 的位置上是奇数。 要是 `arr[mid]` 是偶数，说明 `mid` 的位置上是偶数。 这看起来像是在猜。 实际上不是。 比如数组是 `1, 2, 3, 4, 5`。 我们要找第 2 项是奇数。 `mid = 3`。`arr[3] = 4` 是偶数。 说明第 2 项不是 4。 这如何推断？ 啊，我刚刚理解错了。 二分法在这里的功能是“区间划分”。 你要找的是“在第 n 个位置，值是奇数”。 你每次把区间 `low` 到 `high` 切一半。 要是 `arr[mid]` 的奇偶性和你想要的结局一致，那你持续往 `mid` 缩小的方向走。 要是不一致，那你持续往另一个方向走。 实际上，这就是在利用“奇偶性”这个性质来收窄范围。 比如，假设你要找第 3 项。 区间 `[1, 5]`。 中间是 3。你直接看 `arr[3]` 是奇数。找到了。 假设区间 `[1, 4]`。 中间是 2。`arr[2]` 是偶数。 说明第 2 项是偶数。

那第 3 项呢？它在 `[3, 4]`。 区间 `[1, 5]`，中间是 3。`arr[3]` 是奇数。 说明第 3 项是奇数。 你会发现，这里实际上是在利用区间的中点作为决策器。 要是中点的值符合某种条件，那就缩小范围。 要是不符合，那就换方向。 这个过程，实际上就是不断“舍弃”掉不符合条件的区间。 比如你要找第 3 项。 第一次，你切 `[1, 5]`。你发现 `arr[3]` 是奇数。 这说明，要是目标是奇数，那 `mid` 位置就是答案。 要是目标是偶数，那 `mid` 位置就不是答案，那你就得去 `[3, 4]` 找偶数。 你看，你把 `[3, 4]` 扔掉了，只去了“目标为偶数”的那一半。 出于 `[1, 3]` 里肯定没有偶数了。 故此，二分法不只是是“范围缩小”，它更是利用“中间值”的性质，去“删除”掉不符合条件的数据。 这种本事，在面试里特别有用。 比如问“是不是奇数”。 直接取中点。 要是是，那说明中点知足条件。 要是不是，那说明中点不知足条件。 这时候你就能够直接说“不知足”，然后去另一半找。 这比线性搜索要快得多。 再比如，在 LeetCode 上。 有一道题，让你判断一个二叉树是不是 `2000` 序列。 递归就能做。 要是不用递归，你就要遍历。 遍历的时候，你每次切一半。 这实际上和二分法一模一样。 故此，二分法在计算机科学里，往往不是指“数组的下标”，而是指“数据的状态”。 你能够把数据分成两半，一半是“奇数状态”，一半是“偶数状态”。 你每次取一个样本，判断它归于哪个状态。 要是是，那你就只保留那个状态。 要是是，那你就保留另一个状态。 这个过程，就是不断剔除样本，直到剩下一个。 这就是二分法的本质。 它不是一种特定的查找算法，而是一种“分治”的思维模式。 把一个大难题，拆解成两个中等难题。 把一个小难题，拆解成两个极小难题。 一直拆解，直到无法拆解，直接给出了答案。 在写代码的时候，这种思维模式会让你的代码更简洁。 比如，不用写 `if` 判断，能够用位运算。 `n += n >> 1`。 `n` 变成原来的 `n/2`。 `n` 又变成 `n/4`。 `n` 又变成 `n/8`。 `n` 变成 `n/16`。 一两次，你减去了 16 次。 这就是“削减”的过程。 在面试中，考官喜爱问。 问：“你理解二分法吗？” 你回答：“我理解二分法就是分治。把数据分成两半，猜一半，猜错扔掉一半，直到找到。” 问：“那线性搜索呢？” 你回答：“线性搜索就是遍历，一次比较一个。” 问：“那为啥二分法快？” 你回答：“出于每次比较后，你扔掉了数据的一半，要么扔掉了比较本事的一半。” 问：“有没有啥陷阱？” 你回答：“要是数据是乱序的，二分法就失效了，你得用其他方式。” 问：“二分查找和二分搜索有啥区别？” 你回答：“二分查找是Range Search，你查区间中心。二分搜索是Indexed Search，你查某个具体位置。” 实际上，二分法这种思维，比算法本身更关键。 它让你看到数据的内在结构。 它让你知道，数据是有规律可分的。 它让你知道，有些难题，不需求你每次都“试”，你能够“跳过”。 比如你在写一个文件读取函数。 你要读一个 `file`。 你每次读一个 `chunk`。 要是 `chunk` 忒大，你就把它分成两半。 要是 `chunk` 忒小，你就读全体。 这就是二分法的雏形。 在代码里，你能够写一个函数，处理不同的输入大小。 要是 `n = 1000`，先读一半，再读另一半。 这比读全体要快，出于你只读了两次，而不是三次。 这是“分治”在工程中的体现。 故此，二分法不只是是一种算法。 它是一种看待世界的方式。 看待数据，就是一场“分家”。 看着数据，你把它切成两半。 看着难题，你把它拆解成两个小难题。 看着目标，你把它缩小成一个点。 这种思维方式，别看好办，但贼强大。 它让计算机科学变得有序。 它让数据处理变得高效。 它让我们明白，不是所有事件都要“全知全能”，有时候，舍弃一半，就能拿到一半的精彩。 在写代码的时候，这种思想也能帮助解决一些棘手的难题。 比如，你遇到一个死循环。 你忍不住想，是不是 `mid = (low + high) / 2` 写错了？ 不是。 而是你的 `low` 和 `high` 写错了。 要是 `low` 写成了 `1`，`high` 写成了 `n`。 那你每次 `mid` 都会往中间走。 要是 `low` 写成了 `0`，`high` 写成了 `n`。 那你每次 `mid` 都会往中间走。 要是 `low` 写成了 `1`，`high` 写成了 `n`。 那你每次 `mid` 都会往中间走。 你看，每次你都在“舍弃”数据。 你舍弃了 `1` 到 `mid` 的数据。 你舍弃了 `mid+1` 到 `n` 的数据。 这种“舍弃”的过程，就是二分法。 它让你看到，数据不是静止的，数据是有流动性的。 你不断流动，不断“舍弃”，直到剩下一个。 这就是二分法。 它不是一种复杂的公式，它是一种好办粗暴的“分家”哲学。 只要你能分家，就能找到答案。 只要你能舍弃，就能解决难题。 只要你能舍弃一半，就能让另一半成为冠军。