Алгоритмы: бинарный поиск на отсортированном массиве (реализация на Java)
#java #алгоритмы В этом видео мы рассмотрим реализацию алгоритма бинарного (двоичного) поиска на отсортированном массиве. Такой поиск выполняется гораздо быстрее, чем прямой перебор всех элементов подряд. Сложность такого алгоритма в О-нотации равна O (log N). Важным условием является именно тот факт, что массив должен быть предварительно отсортированным.
Статья по теме: devmark.ru/article/binary-sea...
Пікірлер: 5
Спасибо за видео, только бы хотелось добавить, что бинарный поиск будет работать на любом отсортированном массиве, по возрастания или по убыванию, реализация алгоритма будет отличаться конечно.
Блестательное объяснение. Я правильно понял, что: 1) left & right мы могли бы назвать first & last? 2) Если у нас дан массив {1 2 3 4 5 6 7 8 9}, то left = 1, right = 9, а middle = 5. И когда мы двигаем границу диапазона вправо или влево, то мы переходим от 1 к 2 и от 2 к 3 если сдвигаем границу вправо, и наоборот, от 9 к 8 и от 8 к 7 если сдвигаем границу влево?
@devmark
Ай бұрын
1) да 2) когда мы двигаем границу, то мы всегда отталкиваемся от middle, т.е. от 5 в вашем примере. и если искомое число меньше 5, то ставим right = 4. если искомое число больше 5, то ставим left = 6. То есть всегда выбираем ту половину, где потенциально может быть искомое число, т.к. массив отсортирован.
@anjelomanoranjan
Ай бұрын
@@devmark спасибо.
Очень плохое видео для новичков в алгоритмах, абсолютно ничего не объясняется. Но для того, чтобы освежить в памяти, для тех, кто и так знает - норм