关于二分查找的两个技术问题：最坏情况及O(log n)时间的元素位置

嘿，这俩问题都是二分查找的基础核心点，我来给你唠明白：

1. 请问二分查找算法的最坏情况是什么？ #

二分查找的最坏情况分两种典型场景：

• 目标元素根本不在数组里：这时候你得把搜索范围一次次砍半，直到范围缩小到空，才能确定找不到目标。
• 目标元素位于数组的最边缘（第一个或最后一个位置）：比如找数组的第一个元素，每次你都得比较到搜索范围的最后一步，才能定位到它。

说白了，最坏情况就是你需要执行最多的比较次数，这时候的比较次数是⌈log₂n⌉ + 1（n是数组长度），不过哪怕是最坏情况，二分查找的时间复杂度依然是O(log n)，只是这是这个复杂度下的最大执行次数。

2. 请问数组中的元素需位于何处，才能使二分查找算法的运行时间达到O(log n)？ #

其实这个问题的核心不是元素的位置，而是数组本身的特性：

• 首先数组必须是有序的（升序或者降序都可以，但要和你的查找逻辑匹配，比如你写的是升序查找逻辑，数组就得是升序排列）；
• 其次数组得支持随机访问（比如常规的数组结构，能直接通过索引快速定位元素，像链表这种只能顺序访问的结构就不行）。

只要满足这两个前提，不管目标元素在数组的哪个位置（中间、边缘，甚至不存在），二分查找的时间复杂度都是O(log n)。哪怕是最坏情况，也不会突破这个量级。

内容的提问来源于stack exchange，提问作者mstjepan