слушай ты большой молодец , я недавно начал учить джаву , сильно помог разобраться , забей что просмотров мало , этот видос будут смотреть нормальные люди которые хотят развиваться, таких мало. если можно скинь вк или что еще вижу ты разбираешься в джаве , мб обьяснишь пару тем.
Привет, стараюсь) Хочу создать самые понятные ролики на UA-cam, может со временем получится. При этом не хочется, чтоб блог скатился в очередной банальный обучающий курс, коих и так полон интернет) VK есть на главной странице.
То что двоичный поиск сам по себе эффективней линейного это понятно. Но для его запуска нужно предварительно отсортировать массив и в связи с этим возникает вопрос: насколько эффективней двоичный поиск + предварительная сортировка массива по сравнению с линейной сортировкой?
Ключевой момент в том, что можно отсортировать данные один раз и в таком виде хранить. После этого можно постоянно использовать быстрый двоичный поиск. Так работают базы данных - для полей, по которым часто происходит поиск, строятся отсортированные индексы.
@@arhitutorials Спасибо за ответ. Еще вопрос: в результате мы решаем задачу проверки наличия искомого элемента в первичном массиве, а не его позиции как поставлена задача в 0:45, потому что мы получаем индекс элемента в отсортированном массиве, который никак не коррелирует с индексом этого же элемента в первичном массиве?
@@gessgess6186 Если надо найти индекс в первичном массиве, то можно составить массив из структур вида {элемент, его индекс в первичном массиве}, потом сортировать его по элементам. А потом искать в нем двоичным поиском. При нахождении структуры с элементом, находим так же и его оригинальный индекс. Так обычно и делают. Первичный массив не сортируют, а делают отдельный массив {значение, индекс} и уже с ним работают. Потому что обычно элементы имеют сложную структуру и искать часто надо по нескольким полям. Например, в массиве сотрудников можно искать и по фамилии и по номеру телефона, плюс там обычно куча других полей: адрес, должность, зарплата и т.д. Порядок при сортировке по фамилии и телефону будет разный. Чтоб не делать для поиска две копии массива, отсортированных по разным полям, делают так: массив оставляют как есть, а создают два новых массива {фамилия, индекс} и {телефон, индекс} и уже их сортируют и в них ищут. Найдя индекс берут полную запись по индексу из основного массива. Вот как-то так. По этому при проектировании базы данных хорошо бы заранее предусмотреть, по каким полям в таблице будет нужен поиск, чтоб построить для полей индексы.
Да, правильно. Причем логарифм будет по основанию 2, если массив делится пополам. То есть для двоичного поиска в массиве размером N понадобится не более log2(N) шагов для поиска любого элемента.
Для работы алгоритма не обязательно, чтоб опорный элемент для разделения выбирался четко по середине массива. По этому любой массив можно сортировать. Другое дело, что для любого разделения можно придумать неудачный массив, на котором производительность просядет до n^2. Это недостаток данной сортировки.
@@arhitutorials не совсем понял про сложность О(n^2) для бинарного поиска... Ведь если массив отсортирован, то поиск всегда будет по О(log по основанию 2 от n). Ну а если не отсортирован, то учитывается худшая сложность для сортировки самого наилучшего способа "пирамидальный способ", у которой она равна О(N*LogN). Даже тогда сложность общая будет равна О(LogN+ NLogN), но никак не О(N^2)... Или что вы имели ввиду?
@@Chekist2008 Да, правильно. Сорри, я перепутал, не прочитал заголовок видео, подумал речь идет о быстрой сортировке. Хочу уточнить. Если массив не отсортирован, то линейный поиск за O(N). Если отсортировать, то используем бинарный поиск за log(N), да. Но так как сортировка выполняется только один раз, а искать потом можно сколько угодно, то я бы не стал складывать время сортировки и время поиска. Еще в некоторых случаях отсортировать массив можно за O(N), например используя поразрядную сортировку, или сортировку подсчетом. Скоро сделаю про это видео.
Так это ж эквивалентные выражения (start + end) / 2 = start + (end - start)/2 то есть просто немного в другой форме записано то же самое. Может я думал о длине массива, когда писал. То есть middle - это start + пол длины подмассива.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
спасибо огромное! ваши видео мне очень помогают в обучении!
Спасибо. Гениально. Сильно выручил
Как всегда на высоте!!!!
Спасибо за ваши видео, очень помогает понимать.
Спасибо, все ясно и понятно!
12:16 а почему 16 в ячейке 0? разве не в 6-й должно быть?
Благодарю!
отлично спасибо!
слушай ты большой молодец , я недавно начал учить джаву , сильно помог разобраться , забей что просмотров мало , этот видос будут смотреть нормальные люди которые хотят развиваться, таких мало. если можно скинь вк или что еще вижу ты разбираешься в джаве , мб обьяснишь пару тем.
Привет, стараюсь) Хочу создать самые понятные ролики на UA-cam, может со временем получится. При этом не хочется, чтоб блог скатился в очередной банальный обучающий курс, коих и так полон интернет)
VK есть на главной странице.
То что двоичный поиск сам по себе эффективней линейного это понятно. Но для его запуска нужно предварительно отсортировать массив и в связи с этим возникает вопрос: насколько эффективней двоичный поиск + предварительная сортировка массива по сравнению с линейной сортировкой?
Ключевой момент в том, что можно отсортировать данные один раз и в таком виде хранить. После этого можно постоянно использовать быстрый двоичный поиск.
Так работают базы данных - для полей, по которым часто происходит поиск, строятся отсортированные индексы.
@@arhitutorials Спасибо за ответ. Еще вопрос: в результате мы решаем задачу проверки наличия искомого элемента в первичном массиве, а не его позиции как поставлена задача в 0:45, потому что мы получаем индекс элемента в отсортированном массиве, который никак не коррелирует с индексом этого же элемента в первичном массиве?
@@gessgess6186 Если надо найти индекс в первичном массиве, то можно составить массив из структур вида {элемент, его индекс в первичном массиве}, потом сортировать его по элементам. А потом искать в нем двоичным поиском. При нахождении структуры с элементом, находим так же и его оригинальный индекс.
Так обычно и делают. Первичный массив не сортируют, а делают отдельный массив {значение, индекс} и уже с ним работают. Потому что обычно элементы имеют сложную структуру и искать часто надо по нескольким полям. Например, в массиве сотрудников можно искать и по фамилии и по номеру телефона, плюс там обычно куча других полей: адрес, должность, зарплата и т.д. Порядок при сортировке по фамилии и телефону будет разный. Чтоб не делать для поиска две копии массива, отсортированных по разным полям, делают так: массив оставляют как есть, а создают два новых массива {фамилия, индекс} и {телефон, индекс} и уже их сортируют и в них ищут. Найдя индекс берут полную запись по индексу из основного массива.
Вот как-то так. По этому при проектировании базы данных хорошо бы заранее предусмотреть, по каким полям в таблице будет нужен поиск, чтоб построить для полей индексы.
@@arhitutorials Спасибо за исчерпывающий ответ и спасибо за ваш канал, желаю успехов в его дальнейшем развитии.
спасибо за видео
Большое спасибо за урок ,хорошо объяснишь сделай новые уроки Like и Подписка
Спасибо!
А почему нельзя написать middle = end/ 2 ? ведь это как бы длина деленная на 2, где в итоге получили бы серединку.
Спасибо, просто и понятно. Я правильно понимаю, что сложность двоичного поиска log(N)?
Да, правильно. Причем логарифм будет по основанию 2, если массив делится пополам. То есть для двоичного поиска в массиве размером N понадобится не более log2(N) шагов для поиска любого элемента.
Чему будет равен middleIndex в 34 строке при длине массива, скажем 8? Бинарный поиск подходит и для массива с четным количеством элементов и нечетным?
Для работы алгоритма не обязательно, чтоб опорный элемент для разделения выбирался четко по середине массива. По этому любой массив можно сортировать.
Другое дело, что для любого разделения можно придумать неудачный массив, на котором производительность просядет до n^2. Это недостаток данной сортировки.
@@arhitutorials не совсем понял про сложность О(n^2) для бинарного поиска... Ведь если массив отсортирован, то поиск всегда будет по О(log по основанию 2 от n). Ну а если не отсортирован, то учитывается худшая сложность для сортировки самого наилучшего способа "пирамидальный способ", у которой она равна О(N*LogN). Даже тогда сложность общая будет равна О(LogN+ NLogN), но никак не О(N^2)...
Или что вы имели ввиду?
@@Chekist2008 Да, правильно. Сорри, я перепутал, не прочитал заголовок видео, подумал речь идет о быстрой сортировке.
Хочу уточнить. Если массив не отсортирован, то линейный поиск за O(N). Если отсортировать, то используем бинарный поиск за log(N), да. Но так как сортировка выполняется только один раз, а искать потом можно сколько угодно, то я бы не стал складывать время сортировки и время поиска.
Еще в некоторых случаях отсортировать массив можно за O(N), например используя поразрядную сортировку, или сортировку подсчетом. Скоро сделаю про это видео.
@@arhitutorials Спасибо огромное, теперь все понятно
Почему middle = start + (end - start) / 2 а не middle = start + end / 2?
Так это ж эквивалентные выражения
(start + end) / 2 = start + (end - start)/2
то есть просто немного в другой форме записано то же самое. Может я думал о длине массива, когда писал. То есть middle - это start + пол длины подмассива.
Можно пожалуйста узнать, что это за текстовый редактор?
Это IntelliJ IDEA community edition, можно скачать бесплатно без смс)
@@arhitutorials благодарю
Печать индекса очень актуально ...
int mid = (low + high) / 2; не верная реализация
int mid = low + ((high - low) / 2); верная реализация
Итак, исходное выражение:
mid = low + ((high - low) / 2)
умножаем все на 2, получаем:
2 * mid = 2 * low + high - low
вычитаем 2 * low - low, получаем:
2 * mid = low + high
теперь выражаем mid:
mid = (low + high) / 2
таким образом:
mid = low + ((high - low) / 2)
это то же самое, что
mid = (low + high) / 2
выражения эквивалентны, все верно.