Давайте представим два массива, как это: [8,2,3,4,9,5,7]Двоичный поиск с зазорами
[0,1,1,0,0,1,1]
Как выполнить бинарный поиск только в цифрах с 1 под ним, игнорируя остальные? Я знаю, что это может быть в сравнении O (log n), но мой текущий метод медленнее, потому что он должен пройти через все 0, пока он не достигнет отметки 1.
Если вы нажмете число с 0 ниже, вы необходимо сканировать в обоих направлениях для номера с 1 ниже, пока вы его не найдете, или местное пространство поиска исчерпано. Поскольку сканирование 1 является линейным, отношение 0s к 1s определяет, может ли полученный алгоритм быть быстрее, чем линейный.
O (n) худшая временная сложность не имеет смысла для двоичного поиска. Существуют ли более эффективные способы? – Imnewhere
Ну, я думаю, что все еще O (log n), если у вас есть только log (n) нулей. Если у вас больше нулей, поиск их будет доминировать, и вы приблизитесь к линейному времени. Проблема в том, что значения с 0s не сортируются, поэтому вы не можете использовать двоичный поиск, чтобы пропустить их. Следовательно, если их слишком много, их пропуск будет доминировать над общим временем. –
Это большая проблема. Я пытаюсь создать алгоритм сортировки O (nlogn), который выполняет только n свопов. Мне нужно выполнить этот двоичный поиск n раз, поэтому, если каждый поиск O (n) в худшем случае (все равны 0s), его производительность будет приблизительно соответствовать квадрату O (n). Я занимаюсь немного больше исследований, возможно, мне нужна другая структура данных. – Imnewhere
Я не это имел в виду. Я хочу сделать двоичный поиск в первом массиве, но ТОЛЬКО к числам, которые имеют 1 в одном и том же индексе второго массива, игнорируя остальные, поэтому не имеет значения, остальное если отсортировано или нет. – Imnewhere
Сам двоичный поиск - O (log n), но для этого требуется сортировка входного массива. Сортировка может быть выполнена в O (n * log n), а фильтрация значений, связанных с 1s во втором массиве, может быть выполнена в O (n). Следовательно, общий алгоритм будет O (n * log n). Вы не можете сделать лучше, чем при двоичном поиске. – Jubobs
Я объясню это по-другому: вот такой же пример, как и раньше: [8,2,3,4,9,5,7] [0,1,1,0,0,1,1] Если мы игнорировать числа в первом массиве с 0 ниже, первый массив будет выглядеть так [2,3,5,7], он сортируется, поэтому мы можем выполнять двоичный поиск. Цель состоит в том, чтобы игнорировать остальную часть чисел – Imnewhere