提高函数的时间复杂度，以返回列表中第一个元素的索引。

Question

更新1（10月16日）：原始代码有一些逻辑错误，已更正。下面更新的代码现在应该为所有列表L、S、T生成正确的输出，它们满足特殊列表的标准。你知道吗

我正在尝试减少以下函数的运行时间：

“firstrepeat”函数接受一个特殊的列表L和一个索引，并产生最小的索引，使得L[i]==L[j]。换句话说，不管L[i]处的元素是什么，“firstrepeat”函数返回列表中该元素第一次出现的索引。你知道吗

---

列表L有什么特别之处？：

• 列表可以在列表的递增侧或递减侧包含重复的元素，但不能同时包含这两个元素。i、 e[3,2,1,1,1,5,6]很好，但不是[4,3,2,2,1,2,3]

• 列表是先减少（或保持不变），然后增加（或保持不变）。

• 示例：

  L = [4,2,0,1,3] 
  L = [3,3,3,1,0,7,8,9,9]
  L = [4,3,3,1,1,1]
  L = [1,1,1,1]
  

---

输出示例：

假设我们有L=[4,3,3,1,1,1]

firstrepeat（L，2）将输出1

firstrepeat（L，5）将输出3

---

我有以下代码。我相信复杂性是O（logn）或更好（尽管我可能遗漏了一些东西）。我正在寻找改善时间复杂性的方法。你知道吗

def firstrepeat(L, i):
    left = 0
    right = i
    doubling = 1
    #A Doubling Search
    #In doubling search, we start at one index and then we look at one step 
    #forward, then two steps forward, then four steps, then 8, then 16, etc. 
    #Once we have gone too far, we do a binary search on the subset of the list 
    #between where we started and where we went to far.
    while True:
        if (right - doubling) < 0:
            left = 0
            break
        if L[i] != L[right - doubling]:
            left = right - doubling
            break
        if L[i] == L[right - doubling]:
            right = right - doubling
            doubling = doubling * 2
    #A generic Binary search
    while right - left > 1:
        median = (left + right) // 2
        if L[i] != L[median]:
            left = median
        else:
            right = median

    f L[left] == L[right]:
        return left
    else: 
        return right