Алгоритмы «разделяй и властвуй» — вариант бинарного поиска

Это практический вопрос для понимания алгоритмов «разделяй и властвуй».

Вам дан массив из N отсортированных целых чисел. Все элементы различны, за исключением того, что один элемент повторяется дважды. Разработайте алгоритм O (log N), чтобы найти этот элемент.

Я понимаю, что этот массив нужно разделить и посмотреть, не будет ли найден равный аналог в следующем индексе, какой-то вариант бинарного поиска, я полагаю. Но я не могу найти никакого решения или руководства по этому поводу.


algorithm binary-search divide-and-conquer
person someone    schedule 06.12.2015    source источник
comment
Это последовательные целые числа?   -  person Mark Ransom    schedule 06.12.2015
comment
Нет. Это точный текст вопроса, и в нем не упоминаются последовательные целые числа.   -  person someone    schedule 06.12.2015
comment
Я не думаю, что есть решение logN, когда это не последовательные числа.   -  person Idos    schedule 06.12.2015
comment
Для достижения log(N) вам нужен критерий для отбрасывания половины массива на каждой итерации. Со случайными (хотя и отсортированными) целыми числами такого критерия нет, и вам нужно в конечном итоге проверить все элементы, что делает наихудший случай O (N). Возможно, автор вопроса имел в виду массив из 1..N-1 элементов (т.е. последовательных).   -  person LSerni    schedule 06.12.2015
comment
Это кажется слишком похожим на вопрос о последовательных числах, возможно, он был пропущен по ошибке, поскольку, если нет, то вопрос о последовательном отсортированном массиве имеет избыточную информацию, а ее нет :)   -  person Ron.B.I    schedule 06.12.2015
comment
Мои мысли точно. Если бы это было так, мы бы сравнили элемент с индексом и соответственно отбросили бы половину массива.   -  person someone    schedule 06.12.2015

Ответы (2)


arrow_upward
3
arrow_downward

Вы не можете сделать это за время O(log n), потому что на любом шаге, даже если вы разделите массив на 2 части, вы не можете решить, какую часть учитывать для дальнейшей обработки, а какую оставить. С другой стороны, если все последовательные числа присутствуют в массиве, то, глядя на индекс и значение в индексе, мы можем решить, находится ли повторяющееся число в левой или правой части массива.

person Ashu    schedule 06.12.2015

arrow_upward
0
arrow_downward

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) для этой задачи не представляется возможным.

person noname    schedule 10.10.2019