二分查找变形问题

何为二分查找？

折半查找法是一种适用于有序列表快速定位目标项的高效搜索算法

二分查找的查找流程是将位于数组中间位置的元素值与目标特定值进行比较操作。如果中间元素值小于目标值，则需要在数组右侧区域继续执行二分查找；若大于目标值，则转向左侧区域继续进行；当两者相等时，则返回该元素的数组索引位置。

通过查看示意图可以看到对于一个包含n个元素的数组在执行第一次折半查找操作后其有效范围缩减至n的一半随后再次执行折半查找操作则会将当前范围进一步缩减至原来的一半即n/4以此类推经过连续k次折半查找操作之后最终能够确定唯一的目标元素其对应的范围缩小至1

最终得出\frac{n}{2^{k}}=1 ，也就是k=\log n ，这里默认底数是2 。由此可见 ，二分查找算法其时间复杂度属于O(\log n) 。这种极为高效的算法举个例子来说 ，即使面对一百万