Question

c++中的算法 折半查找法（二分法）

Answer 1

假设有n个数已按照 升序（这是关键！） 放在一维数组a中，如何找到你想要的数呢？

二分法，顾名思义，把一段数字分成两半。
你要的数在 已经按照升序排好了 并且的情况下与中间数进行对比有4种情况：

为什么在发现数x比中间数大/小之后，设定left=mid+1和right=mid-1?而不能是left=mid和right=mid?

这就牵扯到如果中间数有两个（如示意图中的第一次循环的中间数为21、25），那么系统会自动选 左边 的那个数作为中间数（21）。
那么当需要检索的是 最末尾的数 ，而最后就剩两个边界，那么无论怎么取中间数，左右边界的范围都不会改变，左边界还是左边界。而你需要检索的数是右边界，即使数确实比中间数大，但是因为算法，中间数永远都不会是右边界，所以永远都不会找到右边界的数。

但是如果设定为left=mid+1和right=mid-1，这种情况就能够使左边界=右边界，中间数就等于那个数，从而能够进行比较、找到。