二分算法（1）

今日，我将为大家梳理二分查找算法的核心理念，并结合三道典型例题进行解析。

二分算法的基本思想：

【二分法是一种极为高效的算法，常被应用于计算机的查找操作中。

先来玩一个趣味的小游戏。假设有一个小于100的正整数x，由你来猜测，而在猜测过程中会提供大小关系的提示，那么如何才能最快地猜中这个数字呢？

最快速的方法是先猜测50，若恰好猜中，则游戏结束；如果猜大了，则向更小的方向继续猜测，比如25；如果猜小了，则向更大的方向进行猜测，比如75；……每次猜测都能将可能的数值范围减少一半，从而逐步接近目标数字。这种思路正是二分法的核心理念。通过这种方式，所有的操作都可以基于2的幂次方来实现，因此其效率远高于逐个枚举的方式。

在使用二分法进行查找时，所处理的数据结构必须为有序数组，即数组中的元素按照其值的大小顺序排列。其基本原理是首先确定待查找数据所在的范围（可以表示为[left, right]区间），然后通过不断缩小范围直至找到目标元素或确认该元素不存在。具体操作如下：首先选取数组中间位置（mid = (left + right) / 2）的元素，并将其与给定值进行比较。若相等，则查找成功；否则，若给定值比该元素小（或大），则目标值必然位于数组的前半部分[left, mid - 1]（或后半部分[mid + 1, right]）。接下来，在新的范围内重复上述过程。如此循环往复