如何高效查找无序二进制向量中的首个1？

首先明确核心结论：不存在最坏时间复杂度严格介于O(log n)和O(n)之间的算法，但可以设计平均/期望时间复杂度更优的策略，在大多数实际场景中表现远好于线性搜索，满足你的需求。

一、最坏情况的下界说明 #

因为你要找的是最左边的1，对于任意算法，都存在极端输入场景：前n-1个元素全为0，最后一个元素是1。这种情况下，算法必须逐一检查完前n-1个0才能确定结果，所以最坏时间复杂度的下界是Ω(n)——不可能比线性搜索的最坏情况更好。

二、平均/期望复杂度更优的实用策略 #

1. 跳跃搜索变种 #

操作逻辑：

• 设定跳跃步长为√n（也可根据实际场景调整）；
• 从起点开始，每次跳√n步检查当前位置：
  • 如果是1，就从上次跳跃的起点到当前位置之间，线性搜索找最左边的1；
  • 如果是0，继续跳跃；
• 直到找到包含1的区间，或者遍历完整个向量。
• 平均时间复杂度为O(√n)，刚好介于O(log n)和O(n)之间，且实现简单。

2. 指数搜索变种 #

操作逻辑：

• 从索引1开始，每次将索引翻倍（2→4→8→…），直到找到第一个索引k使得V[k] = 1；
• 然后在区间[k/2, k]内，从左到右线性搜索，找到该区间内最左边的1（也就是整个向量的首个1）；
• 如果直到向量末尾都没找到1，说明向量全为0。
• 若首个1出现在第m位（m远小于n），时间复杂度为O(log m + m)，接近O(log n)；最坏情况仍为O(n)，但实际表现远优于线性搜索。

3. 概率随机采样策略（适用于1有一定出现概率的场景） #

操作逻辑：

• 随机采样向量中的若干位置：
  • 若采样到1，立即从该位置往左线性搜索，找到最左边的1；
  • 若连续多次采样都是0，再从左到右开始线性遍历；
• 这种方法的期望时间复杂度取决于1的分布概率，比如当1的出现概率为p时，期望采样次数为1/p，再加上往左搜索的平均长度，整体期望复杂度可能远低于O(n)。

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