分治算法-二进制搜索变体

Question

这是一道理解分治算法的练习题。

您将得到一个由N个排序整数组成的数组。除了一个元素外，所有元素都是不同的元素重复两次。设计一个O（logN）算法来查找该元素。

我知道这个数组需要被划分，看看在下一个索引中是否找到了相等的对应项，我相信这是二进制搜索的变体。但我找不到任何解决方案或指导。

Answer 1

您不能在O（logn）时间内完成，因为在任何步骤中，即使您将数组分成两部分，您也无法决定要考虑哪个部分进行进一步处理，哪个部分应该保留。另一方面，如果连续的数字都存在于数组中，那么通过查看索引和索引中的值，我们可以决定重复的数字是在数组的左侧还是右侧。

Answer 2

D&C应该看起来像这个

int Twice (int a[],int i, int j) {
    if (i >= j)
       return -1;
    int k = (i+j)/2;
    if (a[k] == a[k+1]) 
       return k;
    if (a[k] == a[k-1])
       return k-1;
    int m = Twice(a,i,k-1);
    int n = Twice(a,k+1,j);
    return m != -1 ? m : n;
}

int Twice (int a[], int n) {
    return Twice(a,0,n);
}

但它具有复杂性O（n）。如上所述，对于这个问题，不可能找到O（lg n）算法。