Будет ли работать бинарный поиск, если в массиве есть пробелы?

Question

[Айнур Ярулин]

Здравствуйте, будет ли в таком массиве работать бинарный поиск?
[1, 4, 5, 6, 12, 13, 27 и тд.]
Если нет, то какой еще способ можно реализовать помимо линейного?

Comments

[otdameskapizm]

А что с этим массивом не так?

[mayton2019]

Довольно странный вопрос. Если допустить что массив "без пробелов" тоесть все 27 чисел в нем присутсвтуют

[1,2,3,.....27]

то тогда бинарный поиск вырождается и превращается в проверку на попадание числа в Range.

[Odissey Nemo]

Бинарный поиск работает верно, если массив чисел отсортирован (для определённости - по возрастанию). Сами числа могут принимать любые значения из диапазона своего типа. Скажем, целые знаковые 4-х байтовые (в Java это int) имеют диапазон [-2147483648..2147483647], т.е. от отрицательного минимума до положительного максимума.
Числа могут повторяться и разница между соседями может быть произвольной. Главное - последовательность не должна убывать.

Answer 1

[Wataru]

Будет. Бинарному поиску главное, чтобы числа в массиве не убывали. Даже если там числа больше предыдущего не только на 1.

Answer 2

[Mercury13]

Что такое вообще «пробелы»?
1. Пробелы в исходном коде: за пределами закавыченных строк это только оформление и в исполнении не участвует. Ну и слова, разумеется, нужно разделять пробелами — как в паскалевском «packed array» или сишном «int main».
2. Пропуски: не 1,2,3, а 1,4,5. Да, для этого бинарный поиск и предназначен: массив отсортирован, никаких других правил нет, найти или сам элемент, или место, куда вставить его.
Например, ищем 7: 6 → больше, 13 → меньше, 12 → меньше. Не нашли; если нужно вставить — то после 6-ки.
Ищем 1: 6 → меньше, 4 → меньше, 1 → попали.

Comments

[Айнур Ярулин]

Спасибо