Question

二分查找

Answer 1

二分查找也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构。他的思想很简单，但是在书写过程中如果边界条件无法正确的确定，很容易 陷入到循环中无法跳出 。

二段性是集合中的元素有存在 分界线 ，给定条件可以将集合中元素分为两部分，一部分满足条件，一部分不满足条件。

对于一个给定的数组 进行二分查找时，需考虑以下步骤

面对 查找小于 的最后一个数 时，如果令左边界的值为 ，那么左边界的初始条件已经不满足问题要求了，因此采用0作为一个通用的二分求解方法的左边界并不是一个合理的方案。

同理，面对 查找大于 的第一个数 ，也不可以令右边界的值为1。

采用其他的公式，比如 ，也是可以的，但是为了防止 与 相加 导致的数值溢出 使用上面的公式。

为了避免写出死循环， 必须保证每次进入 之后，可行区间都在变小，且最终推出循环 。在此先引出程序终止的条件为 ，当面对 ，此时以满足终止条件所以无论 和 取多少，都会退出循环；当面对 ，中点为 ，此时循环体内的收缩公式会将 赋值给 或者 ，再此达到终止条件，退出循环；当面对 ，按照 里的分析，其最终会进入到 或者 的条件。

因为的目标时遍历整个数组，因此 终止条件要确保所有的元素都可以被包含在内 。同上面的收缩区间的公式相配合可以构成一个二分查找。

和 的指向哪个数值，最终还是取决于judge条件。对于我们要查找小于零第一个数，其judge条件为 ， ， 。

参考文献：