Спасибо огромное за видео! Пожалуйста, объясните для чайника, когда мы пишем l = m+1, r = m - 1; а когда просто приравниваем m? Первый случай только для поиска конкретного элемента?
Мы начали с такого примера и такого решения потому, что для начинающих зрителей они являются более понятными и естественными. Далее мы придём к более общему решению. Задача, которая решается при помощи бинпоиска, чаще состоит не в том, чтобы найти какое-то заданное значение, а в том, чтобы найти первый или последний элемент, обладающий определённым свойством. Для таких задач уже проще запомнить общее решение, когда цикл while идёт до 2 элементов, а l и r всегда смещаются на m (без +1/-1). Подробнее об этом рассказано в следующем видео: ua-cam.com/video/_u2yypDA6R0/v-deo.html Когда нужен поиск заданного значения в массиве, его можно выполнять так, как показано здесь, но можно воспользоваться и вышеупомянутой общей схемой, например, искать первый элемент, который больше или равен заданному значению (цикл while в этом случае идёт до 2 элементов, l и r смещаются на m).
Спасибо за наблюдательность, здесь на слайдах ошибка. Правильная последовательность шагов при поиске элемента 33: L = 0, R = 19, M = 9; A[M] > 33, смещаем R на M - 1 L = 0, R = 8, M = 4; A[M] < 33, смещаем L на M + 1 L = 5, R = 8, M = 6; A[M] > 33, смещаем R на M - 1 L = 5, R = 5, M = 5; A[M] < 33, смещаем L на M + 1 L = 6, R = 5; индексы зашли друг за друга, следовательно, элемента 33 в массиве нет.
Спасибо огромное за видео! Пожалуйста, объясните для чайника, когда мы пишем l = m+1, r = m - 1; а когда просто приравниваем m? Первый случай только для поиска конкретного элемента?
Мы начали с такого примера и такого решения потому, что для начинающих зрителей они являются более понятными и естественными. Далее мы придём к более общему решению.
Задача, которая решается при помощи бинпоиска, чаще состоит не в том, чтобы найти какое-то заданное значение, а в том, чтобы найти первый или последний элемент, обладающий определённым свойством. Для таких задач уже проще запомнить общее решение, когда цикл while идёт до 2 элементов, а l и r всегда смещаются на m (без +1/-1). Подробнее об этом рассказано в следующем видео: ua-cam.com/video/_u2yypDA6R0/v-deo.html
Когда нужен поиск заданного значения в массиве, его можно выполнять так, как показано здесь, но можно воспользоваться и вышеупомянутой общей схемой, например, искать первый элемент, который больше или равен заданному значению (цикл while в этом случае идёт до 2 элементов, l и r смещаются на m).
@@op_ulstu благодарю! Вы один из топовых авторов по объяснению алгоритмов.
3:10 - почему сдвинули R на 40, а не на 43?
Спасибо за наблюдательность, здесь на слайдах ошибка.
Правильная последовательность шагов при поиске элемента 33:
L = 0, R = 19, M = 9; A[M] > 33, смещаем R на M - 1
L = 0, R = 8, M = 4; A[M] < 33, смещаем L на M + 1
L = 5, R = 8, M = 6; A[M] > 33, смещаем R на M - 1
L = 5, R = 5, M = 5; A[M] < 33, смещаем L на M + 1
L = 6, R = 5; индексы зашли друг за друга, следовательно, элемента 33 в массиве нет.
@@op_ulstu понял, большое спасибо за уточнение! И за курс в целом - он отличный!
Топ