[Играет музыка] 

ДАГ Lloyd: Ладно. Так бинарный поиск является Алгоритм можно использовать найти элемент внутри массива. В отличие от линейного поиска, он требует особое состояние быть выполнены заранее, но это так гораздо более эффективным, если это условие, на самом деле, встретились. 

Так что идея здесь? это разделяй и властвуй. Мы хотим, чтобы уменьшить размер область поиска на половину каждого времени Чтобы найти номер адресата. Это где это условие вступает в игру, хотя. Мы можем только использовать возможности устраняя половины элементов даже не глядя на им, если массив отсортирован. 

Если это полная путаница, Мы не можем просто из рук отбросить половину элементов, так мы не знаем, что мы отбрасывая. Но если массив отсортирован, мы можем сделать это, потому что мы знать, что все в оставили, где мы в настоящее время должна быть ниже, чем значение мы в настоящее время. И все к Право, где мы должна быть больше, чем значение мы в настоящее время смотрит. 

Так что псевдокод шаги для бинарного поиска? Мы повторяем этот процесс до тех пор, массив или, как мы пройти через, суб массивы, мелкие кусочки исходный массив, имеет размер 0. Рассчитать среднюю текущего подобласти. 

Если значение, которое вы ищете, в этом элементе массива, остановиться. Ты нашел это. Замечательно. В противном случае, если цель меньше, чем то, что в середине, так что если значение, которое мы ищем для меньше, чем то, что мы видим, повторить этот процесс еще раз, но изменить конечную точку, а не бытия оригинал завершить полный спектр, чтобы быть только слева где мы просто смотрели. 

Мы знали, что средняя была слишком высокой, или цель была меньше, чем в середине, и поэтому он должен существовать, если он вообще существует в массиве, где в левой части середины. И поэтому мы будем устанавливать массив место только для левой от средней точки в качестве нового конечного пункта. И наоборот, если цель больше, чем то, что в середине, мы делаем точно такой же процесс, но вместо этого мы изменить начальную точку, чтобы быть только справа от середины мы только что вычислили. И тогда мы начинаем процесс снова. 

Давайте себе это, хорошо? Таким образом, есть много всего происходит, и здесь, но вот массив из 15 элементов. И мы собираемся быть отслеживание много больше вещей на этот раз. Таким образом, в линейном поиске, мы были только заботясь о цели. Но в этот раз мы хотим, чтобы заботиться о где мы начинает выглядеть, где мы остановились, глядя, и то, что середина текущего массива. Так вот мы идем с бинарного поиска. Мы довольно много хорошо идти, верно? Я просто хочу, чтобы положить вниз ниже здесь множество индексов. Это в основном только то, что элемент массива мы говорим о. При линейном поиске, мы заботиться, поскольку мы нужно знать, сколько элементы мы Перебор, но мы на самом деле не волнует, что элемент в настоящее время мы смотрим. В бинарного поиска, мы делаем. И так те просто там немного руководства. 

Таким образом, мы можем начать, правильно? Ну, не совсем. Помните, что я сказал, о двоичного поиска? Мы не можем сделать это на несортированный массив или еще, мы не гарантирует, что некоторые элементы или значения не случайного отбрасываются, когда мы просто решили игнорировать половина массива. 

Так шаг один с бинарного поиска это вы должны иметь упорядоченный массив. И вы можете использовать любой из сортировки алгоритмы мы говорили о чтобы вы на эту должность. Так что теперь, мы в таком положении, когда мы можем выполнить бинарный поиск. 

Так давайте повторим процесс шаг за шагом, и держите трек, что происходит, как мы идем. Таким образом, сначала мы должны сделать, это рассчитать середина текущего массива. Ну, мы сказать, что мы, в первую все, глядя на стоимость 19. Мы пытаемся, чтобы найти номер 19. Первый элемент этого Массив расположен с индексом ноль, а последний элемент в этом Массив расположен в индексе 14. И так мы будем называть тех, начало и конец. 

Таким образом, мы вычислить среднюю по добавив 0 плюс 14 деленное на 2; довольно просто середина. И мы можем сказать, что середина сейчас 7. Так 15 то, что мы ищем? Нет, это не так. Мы ищем 19. Но мы знаем, что 19 больше, чем то, что мы нашли в середине. 

Итак, что мы можем сделать, это изменить начальную точку чтобы быть просто справа от середина, и повторить процесс снова. И когда мы это сделаем, мы теперь сказать Новый старт точка расположения массива 8. То, что мы сделали это эффективно игнорируются все слева от 15. Мы ликвидировали половину проблемы, и в настоящее время, вместо того, чтобы искать более 15 элементов в массиве, у нас есть только для поиска более 7. Так 8 является новый старт точка. 14 по-прежнему является конечной точкой. 

А теперь, перейдем это снова. Мы вычисляем новое середину. 8 плюс 14 22, делится на 2 11. Это то, что мы ищем? Нет, это не так. Мы ищем значению, меньше, чем то, что мы только что нашли. Так что мы собираемся повторить процесс снова. Мы собираемся изменить конечную точку для как раз слева от середины. Таким образом, новый конечный пункт становится 10. А теперь, вот только часть массив, мы должны разобраться в. Таким образом, мы уже устранены 12 из 15 элементов. Мы знаем, что, если 19 существует в массиве, это должен существовать где-то между элементом № 8 и № 10 элемент. 

Таким образом, мы вычисляем новое середину снова. 8 плюс 10 18, делится на 2 9. И в этом случае, смотрите, цель в середине. Мы нашли именно то, что мы ищем. Мы можем остановиться. Мы успешно завершили двоичный поиск. Все в порядке. Итак, мы знаем этот алгоритм работает, если цель где-то внутри массива. Означает ли это работать, если алгоритм цель не в массиве? Ну, давайте начнем ее снова, и на этот раз, давайте посмотрим на элемент 16, которые визуально видно, нигде не существует в массиве. 

Начальная точка снова 0. Конечная точка снова 14. Таковы показатели первого и Последние элементы массива. полный И мы будем идти через процесс мы только пошел через раз, пытаясь найти 16, даже если визуально, мы можем уже сказать, что он не собирается быть там. Мы просто хотим, чтобы убедиться, что этот алгоритм будет, на самом деле, до сих пор работают в какой-то мере и не просто оставить нам застрял в бесконечном цикле. 

Так что шаг первым? Рассчитать среднюю текущего массива. Что середина текущего массива? Ну, это 7, верно? 14 плюс 0 разделить на 2, 7. 15 то, что мы ищем? Нет. Это довольно близко, но мы ищем для значения немного больше, чем это. 

Итак, мы знаем, что это будет не быть нигде слева 15. Целевое больше что в середине. И поэтому мы устанавливаем новую начальную точку для как раз справа от середины. Середина в настоящее время 7, так скажем, новую начальную точку 8. И то, что мы фактически сделать еще раз игнорируется вся левая половина массива. 

Теперь мы повторяем обрабатывать еще раз. Рассчитать новую среднюю. 8 плюс 14 22, делится на 2 11. 23 то, что мы ищем? К сожалению нет. Мы ищем значение что меньше, чем 23. И поэтому в данном случае, мы собираемся изменить конечную точку, чтобы быть просто слева от текущего середине. В настоящее время средняя точка 11, и поэтому мы зададим новую конечную точку в следующий раз мы идем через этот процесс до 10. 

Опять же, мы идем через процесс снова. Рассчитать среднюю. 8 плюс 10 делится на 2 9. Есть 19, что мы ищем? К сожалению нет. Мы все еще ищем число меньше. Таким образом, мы изменить конечную точку на этот раз быть просто слева от середины. Середина в настоящее время 9, так что конечная точка будет 8. И теперь, мы просто ищем в одном массиве элемента. 

Что середина этого массива? Ну, он начинается в 8, это заканчивается в 8, середина 8. Это то, что мы ищем? Мы ищем 17? Нет, мы ищем 16. Так что, если он существует в массиве, она должна где-то существовать слева, где мы в настоящее время. Так что же мы будем делать? Ну, мы установить конечную точку, чтобы быть просто слева от текущего середине. Таким образом, мы изменить конечную точку до 7. Вы видите, что только здесь произошло, правда? Посмотрите здесь. 

Начать сейчас больше, чем конец. Фактически, два конца из нашего массива перешли, и начальная точка находится Теперь после того, как в конечной точке. Ну, это не никакого смысла, не так ли? Так что теперь, что мы можем сказать, что мы есть суб массив размером 0. И как только мы добрались до Эта точка зрения, мы можем в настоящее время гарантировать, что элемент 16 не существует в массиве, потому начальной точки и конечная точка перешли. И таким образом это не там. Теперь, обратите внимание, что это немного отличается от точки начала и окончания Суть в том, то же самое. Если бы мы были глядя на 17, это было бы был в массиве, и точки старта и конечная точка этого последней итерации прежде чем эти точки пересекаются, мы бы нашли 17 там. Это только, когда они пересекают, что мы можем гарантировать, что элемент не существует в массиве. 

Итак, давайте много меньше шагов, чем линейный поиск. В худшем случае, мы имели разделить список элементов п неоднократно в половине, чтобы найти цель, либо потому, что целевой элемент будет где-то в последний деление, или он не существует вообще. Таким образом, в худшем случае, мы должны разделить на array-- вы знаете? Журнал п раз; мы должны сократить проблемы в половине определенное количество раз. Это число раз является журнал п. 

Какой самый лучший сценарий? Ну, в первый раз мы рассчитать среднюю, мы находим, что мы ищем. Во всех предыдущих примеры на бинарный поиск мы только что закончилась, если бы мы имели искал элемента 15, мы обнаружили, что немедленно. Это было в самом начале. Это было середина первая попытка раскола дивизии в бинарный поиск. 

И так в худшем так, бинарный поиск работает в журнале п, что значительно лучше, чем линейный поиск, в худшем случае. В лучшем случае, двоичный Поиск работает омега 1. Так бинарный поиск много лучше, чем линейный поиск, но вам приходится иметь дело с процессом сортировка свой массив, прежде чем вы можете использовать силу двоичного поиска. 

Я Дуг Ллойд. Это CS 50.