>> ROB BOWDEN: Привет, я Роб.
Как мы используем бинарный поиск?
Давайте выясним.
Так, обратите внимание, что этот поиск мы собираемся реализовать рекурсивно.
Кроме того, можно реализовать бинарный поиск многократно, так что если вы это сделали,
это совершенно нормально.
>> Теперь сначала, давайте помнить, что Параметры для поиска предназначены для.
Здесь мы видим десятичного значение, которое должно быть значение пользователь
поиск.
Мы видим массив Int ценности, которые это массив, в котором мы
поиск значения.
И мы видим, Int N, который является длина нашего массива.
>> Теперь, первое, что в первую очередь.
Мы проверяем, если п равно 0, в этом случае мы вернуться ложным.
Вот только говорить, если у нас есть пустой Массив, стоимость явно не будет в
пустой массив, поэтому мы можем вернуться ложным.
>> Теперь, мы на самом деле хотим сделать двоичный Поиск часть бинарного поиска.
Так, мы хотим найти середину элемент этого массива.
Здесь мы говорим среднего равна п делится на 2, с середины элемент
будет длина разделить на 2 наш массив.
Теперь мы собираемся, чтобы проверить, если средний элемент равен значению, когда мы находимся
поиск.
Так что, если значения среднего равна стоимости, мы может вернуться верно, поскольку мы обнаружили, что
значение в массиве.
>> Но если это не так, теперь мы должны сделать рекурсивный
шаг бинарного поиска.
Нам нужно искать либо слева от массива или
средний массива.
Так вот, мы говорим, если значения в середине является меньше, чем значение, что означает, что стоимость
было больше, чем в середине массива.
Так значение должно быть справа от элемент, который мы только что смотрели.
>> Так вот, мы собираемся поиск рекурсивно.
И мы будем смотреть на то, что мы передаем к этому в секунду.
Но мы собираемся искать в Право среднего элемента.
А в другом случае, это означает, что значение было меньше, чем в середине
Массив, и таким образом мы собираемся искать влево.
Теперь левая будет немного легче смотреть.
Таким образом, мы видим, что мы рекурсивно вызова поиска, где первый
аргумент, опять же, значение мы ищем более.
Второй аргумент будет Массив, мы искали более.
И последний элемент теперь является средний.
Помните последний параметр является нашим внутр п, так что это длина нашего массива.
>> В рекурсивном вызове для поиска, мы теперь говорят, что длина
массив средний.
Так что, если наш массив был размером 20 и мы Поиск по индексу 10, так как середина
20 разделить на 2, что означает, что мы проходя 10 как новый
длина нашего массива.
Помните, что когда у вас есть массив длиной 10, это означает, что действует
элементы находятся в индексов от 0 до 9.
Так что это именно то, что мы хотим указать наш обновленный массив - левый
Массив из среднего элемента.
>> Так, в поисках к праву немного сложнее.
Теперь сначала давайте рассмотрим длину массива на право
средний элемент.
Так что, если наш массив был размером п, то Новый массив будет иметь размер н минус
средний минус 1.
Итак, давайте думать о н минус середине.
>> Опять же, если массив были размером 20 и мы делим на 2, чтобы получить середину,
так середина 10, то п минус среднего собирается дать нам 10, так 10
элементы справа от середины.
Но у нас есть этот минус 1, так как мы не хотим, чтобы
включают саму середину.
Так н минус средний минус 1 дает нам Общее количество элементов справа
среднего индекса в массиве.
>> Теперь вот, помните, что средний параметром является массив значений.
Так вот, мы передаем обновление значения массива.
Эти значения плюс средний плюс 1 является фактически говоря рекурсивный вызов
Поиск, переходя в новый массив, где что новый массив начинается в середине
плюс один из наших первоначальных значений массива.
>> Альтернативный синтаксис, что теперь, вы начали видеть указатели, является
значения амперсенд среднего плюс 1.
Таким образом, захватить адрес середине плюс один элемент ценностей.
>> Теперь, если вы не были удобны изменения массив, возможно, вам
может также реализовали это, используя рекурсивный вспомогательная функция, где
что вспомогательная функция принимает больше аргументов.
Так вместо того, чтобы только значение, массив, и размер массива,
вспомогательная функция может занять больше аргументы, в том числе более низким индексом
что вы заботитесь о в массиве и верхний индекс, что вы заботитесь
о массиве.
>> И так отслеживания и нижняя индекс и верхний индекс, вы не
нужно постоянно изменять исходные значения массива.
Вы можете просто продолжать использовать массив значений.
Но вот, обратите внимание, мы не нуждаемся в помощника функционировать до тех пор, как мы
готовы изменить оригинал значения массива.
Мы готовы передать в Обновленный значения.
>> Теперь, мы не можем бинарный поиск по массив, который является несортированный.
Итак, давайте получить эту разобраться.
Теперь, обратите внимание, что сортировка последние два параметры десятичного значения, которое является
Массив, мы сортировка и Int N, что длина массива,
мы сортировки.
Итак, вот мы хотим реализовать алгоритм сортировки
что есть о н в квадрате.
Вы можете выбрать пузырь сортировки, отбора сортировать, или сортировка вставками, или
некоторый другой вид у нас не видел в классе.
Но здесь, мы собираемся использовать выбора рода.
>> Так, мы собираемся итерации в течение всего массива.
Ну, вот мы видим, что мы итерации от 0 до п минус 1.
Почему бы не все, вплоть до п?
Ну, если мы уже отсортированы первым п минус 1 элементов, то
самый последний элемент, что уже должно быть в правильном месте, так сортировки по
весь массив.
>> Теперь вспомните, как выбор вроде работает.
Мы собираемся идти в течение всего массива ищу минимального значения в
массив и пряника, что в самом начале.
Тогда мы собираемся идти в течение всего Массив снова ищет второго
наименьший элемент, и палка, что на второй позиции в
массив, и так далее.
Итак, вот что это делает.
>> Здесь мы видим, что мы установки текущего минимума
значение для г-го индекса.
Так на первой итерации, мы собираемся рассмотреть минимальное значение быть
начало нашего массива.
Тогда, мы собираемся для перебора Остальная часть массива, проверка на
увидеть, если есть какие-либо элементы меньше, чем тот, который мы в настоящее время
учитывая минимум.
>> Так вот, значения J плюс один - это меньше, чем то, что мы в настоящее время
учитывая минимум.
Тогда мы собираемся обновить то, что мы думаем, что это минимальный, чтобы
индекс J плюс 1.
Так, сделать это через весь массив, и после этого в течение цикла, минимум
должно быть минимальным элементом из я-ю позицию в массиве.
>> Как только у нас есть, что мы можем поменять Минимальное значение в г-й позиции
в массиве.
Так что это всего лишь стандартный подкачки.
Мы храним во временном значении - значение я-я в массиве -
значение помещается г-й в массиве Минимальное значение, которое принадлежит там,
а затем сохранить обратно в где тока минимальное значение раньше
I-й значение в массиве, так что мы не потеряли его.
>> Так, что продолжается следующая итерация.
Мы начнем искать второго Минимальное значение и вставьте, что в
Вторая позиция.
На третьей итерации, мы будем искать третье значение минимальной и вставка
что в третьем положении, и поэтому , пока у нас нет отсортированный массив.
Меня зовут Боб, и это был выбор рода.