Алгоритм для поиска пересечения отсортированных множеств

Question

Я искал способы найти пересечение двух отсортированных множеств, которые более эффективны, чем так итеративно. В конце концов мой поиск привел меня к этому вопросу: intersection and union of n-arrays in C. Однако я не понимаю, как пересечение двух множеств равно пересечению пересечения двух подмножеств. Я хочу попытаться выяснить, как выполнить алгоритм разделения и покорения с рекурсией, но я не могу понять, как будет работать данный пример.

Более конкретно, как бы разделяй и властвуй алгоритм когда-нибудь работать для двух наборов, таких как:

A = 1, 2, 3, 4 
B = 3, 5, 6, 7 

Это не похоже, разделяй и властвуй алгоритм будет существовать, что бы на самом деле последовательно найти пересечение в 3.

Answer 1

Однако я не понимаю, как пересечение двух множеств равно до пересечения пересечения двух подмножеств.

Это не то, о чем говорит ваша ссылка (потому что это неправильно, как вы признали).

Поиск пересечения отсортированного набора, т.е. общие элементы двух отсортированных массивов,
невозможно, не прерывая их. Он не будет лучше, чем O (N).

Answer 2

Между двумя массивами найдите тот, который последний элемент больше, чем первый элемент другого.

Например:

A = 1, 2, 3, 4 
B = 3, 5, 6, 7 

Выберите массив A. Применить Двоичный поиск по A справа налево, чтобы найти элемент, такие, что:

A[i] >= B[0] 

Теперь используйте линейный поиск из этих двух массивов:

A[i......n] 
B[0......m] 

Где n и m являются длиной A и B соответственно.

Я думаю, что он имеет меньшую сложность, чем линейный поиск с первой попытки.