algorithm - 在以下数组中查找搜索的时间复杂度

Question

有一个非常大的排序数组。在这些元素中，每个元素都重复不止一次，除了一个元素。解决这个问题的最佳算法的最差时间复杂度是多少，并给出该算法

Answer 1

它应该是 log(n)。

给定：排序后的数组，除了一个之外的所有元素都是重复的。然后直到那个单个元素，元素的索引将占据偶数和下一个奇数。在这个单个元素之后，它们将占据奇数和下一个偶数索引。

用这个逻辑开始二分搜索。

bsearch (a, low, high)  
    mid = (low + high)/2  
    if ((a[mid-1] != a[mid]) && (a[mid+1] != a[mid]))  
          return a[mid]
    else
       mid = (mid & ~0x1) //making mid an even index
       if (a[mid] == a[mid+1]) //single element is after this index
                 bsearch (a, mid + 2, high)
       else //element is before this
                 bsearch (a, low, mid-1)

希望这可以帮助