如何在有序无限单词列表中高效查找单词对应索引（优化O(n)时间）

嘿，这个问题挺巧妙的——面对无限的字典序排序列表，普通线性查找O(n)效率太低，常规二分查找又因为没有明确右边界没法直接用。不过我们可以结合「指数扩展找范围」+「二分查找精确定位」的思路，把时间复杂度降到O(log k)（k是目标单词的实际索引），完美解决这个优化需求。

核心思路 #

1. 先锁定区间：从索引1开始，不断将右边界翻倍（1→2→4→8…），直到A.get(right)返回的单词字典序大于目标单词。此时我们能确定目标一定落在[left, right]区间内（left是上一轮的right值）。
2. 二分查找精确定位：在找到的区间内执行标准二分查找，每次取中间索引，对比对应单词和目标的字典序，逐步缩小范围，直到找到匹配的索引。

代码实现 #

class A:
    # 假设原类已实现get方法，此处仅做模拟示例
    def get(self, index):
        # 模拟无限字典序单词列表（实际场景为无限，此处仅展示片段）
        word_list = ["apple", "banana", "cat", "dog", "elephant", "fox", "grape", ...]
        return word_list[index]

    def get_index(self, target):
        # 处理特殊情况：目标是第一个单词
        first_word = self.get(0)
        if first_word == target:
            return 0
        
        # 第一步：指数扩展找到目标所在的区间
        left, right = 0, 1
        while self.get(right) < target:
            left = right
            right *= 2
        
        # 第二步：在区间内执行二分查找
        while left <= right:
            mid = (left + right) // 2
            current_word = self.get(mid)
            
            if current_word == target:
                return mid
            elif current_word < target:
                # 目标在右半区间，调整左边界
                left = mid + 1
            else:
                # 目标在左半区间，调整右边界
                right = mid - 1
        
        # 若目标不在列表中（题目假设存在的话可省略此分支）
        return -1

方案优势说明 #

• 指数扩展阶段仅需O(log k)次get调用，因为每次右边界翻倍，能快速覆盖到目标所在的范围，避免了线性遍历的低效。
• 后续二分查找同样是O(log k)次调用，整体时间复杂度远优于O(n)的线性查找，尤其当目标索引很大时优势极为明显。
• Python字符串原生支持字典序比较（</>/==），正好匹配列表按字典序排序的要求，无需额外处理。

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