“极性反转”是二分查找中的一个重要概念，它适用于满足特定条件的搜索空间：当我们对搜索空间应用二分查找算法时，搜索空间的前后区域状态会发生反转。在这篇文章中，我们将借助一道题目来深入理解二分查找中的“极性反转”概念是如何发挥作用的。
什么是二分查找中的极性反转概念？
在使用二分查找算法解决问题时，我们通常会初始化两个指针——INLINECODEe0af4b6f 和 INLINECODE8f3f13db，它们分别指向搜索空间的起始和结束位置。二分查找的“极性反转”概念指出：如果最初 INLINECODEef83c460 指向的是非解区域（Non-solution region），而 INLINECODE29d30258 指向的是解区域（Solution region），那么在二分查找算法结束后，INLINECODEd4f8b8c0 将指向解区域，而 INLINECODE06aee453 将指向非解区域（反之亦然）。
!Opposite-polarity-concept-in-Binary-Searchdrawio-(1).png)二分查找中的极性反转概念
借助问题深入理解二分查找中的极性反转概念
让我们回顾一下 Koko Eating Bananas（吃香蕉） 这道题，以便更好地理解这个概念。
在这个问题中，我们需要在整个答案空间中找到一个吃香蕉的速度，使得所有的香蕉都能在 H 小时内被吃完。
我们可以考虑上述问题的一个示例：
n = 4, piles = [3, 6, 7, 11], H = 8
应用二分查找算法前的初始配置
- 我们可以说，这个问题的答案将位于 [1, 10^9] 之间。
- 但是，在答案空间中加入一个大于给定数组最大值（在这个例子中是 11）的数字是没有意义的，因为在任何速率下（>=11 根/小时），所需的小时数将总是 4，这在这里是无用的。如果超过 11 的答案空间给出的值与 11 相同且也是无用的，那么最好将其省略。
- 因此，将答案区域取为 [1, 11] 是最优的。这意味着最初，INLINECODE311b18f6 初始为 INLINECODE2ba4400f，而 INLINECODEaba119f0 为 INLINECODE117fb638。
- 这个测试用例的答案是 4（为了便于理解极性反转概念，我们事先知道了答案）。这意味着在速率（=4 根/小时）时，所有香蕉都可以在 8 小时内被吃完。
应用二分查找前的解区域与非解区域
基于以上两点，整个搜索空间被划分为两个区域：
- 解区域： 对于这个问题，解区域是从 [4, 11]，因为在这个速率范围内，我们可以在 8 小时内吃完所有香蕉。由于 INLINECODE3c4a54c3 指向 11，这意味着 INLINECODEebed0eec 最初指向解区域。（注意：实际答案总是位于解区域之间。例如，在 (4-11)/小时 的所有速率下，我们都可以在 8 小时内吃完香蕉。由于题目要求的是最小速率，因此答案是 4）。
- 非解区域： INLINECODEd0e288f5 最初指向 1，它位于非解区域 [1, 3] 中，因为在这个区域内的任何速率下，我们都无法吃完所有的香蕉。因此，INLINECODE718dde37 最初指向非解区域。
使用二分查找算法
- 第一次迭代：
!BS1
- 在这次迭代中 Mid : (1+11)/2 = 6。
- 当速率为 6 根/小时时，吃完所有香蕉所需的时间将 = (3/6)+(6/6)+(7/6)+(11/6) = 1+1+2+2 = 6。
- 这小于或等于 8。所以，这可能是答案，但也可能存在比 6 更小的最小速率，因此移动到 mid 的左侧区域。（注意：在计算小时数时使用了向上取整除法）。
- 第二次迭代：
!BS2
- Mid = (1+5)/2 = 3，吃完所有香蕉所需的时间将 = (3/3)+(6/3)+(7/3)+(11/3) = 1+2+3+4 = 10。
- 所以，这不可能成为答案，因为小时数大于 8，因此移动到 mid 的右侧区域。
- 第三次迭代：
!BS3
- Mid = (4 + 5)/2 = 4。在此速率下所需的小时数将 = (3/4)+(6/4)+(7/4)+(11/4) = 1+2+2+3 = 8。
- 这小于或等于 8。所以 4 可能是答案，但也可能存在更小的每小时速率。
- 因此，将
high移至 mid 的左侧区域。
- 第四次迭代（最后一次迭代）：
!BS4
- 由于 INLINECODE88a93f0d > INLINECODE7d7cd895 不再满足，二分查找在此结束。
应用二分查找后的解区域与非解区域
> 我们可以看到，最初 INLINECODE239b04c2 位于非解区域，而 INLINECODEe2d54adb 位于解区域。但是二分查找结束后，INLINECODE82fd7e3d 变成了 4（指向解区域的边界），而 INLINECODE6271cb87 变成了 3（指向非解区域）。这就是所谓的“极性反转”。
结论： 无论初始状态如何，二分查找算法结束时，INLINECODE4e7b1aee 和 INLINECODEfbe3e30a 指针所指向的区域属性（解/非解）总是会互换，这就是极性反转的核心思想。掌握这一点，能帮助我们更精准地定位二分查找的终止条件和返回值。