>> ZAMYLA Чан: Первое, что вы могли бы уведомление о находке является то, что мы уже
уже код, написанный для нас.
Это называется код распределение.
Таким образом, мы не только написание собственного код с нуля больше.
Скорее, мы заполнения пустот в некотором предварительно существующего кода.
>> Программа find.c запрашивает номера заполнить стог сена, поиск
стоге сена для пользователей представленных иглы, и он делает это путем вызова рода и
поиска, функции, определенные в helpers.c.
Так find.c написано уже.
Ваша задача написать помощников.
>> Так что мы делаем?
Мы реализации две функции.
Поиск, который возвращает истину, если значение находится в стоге сена, возвращаясь
ложным, если значение не в стоге сена.
А потом мы также осуществляет сортировку, которая сортирует массив с именем значения.
Так что давайте решать поиска.
>> Поиск в настоящее время реализован в качестве линейного поиска.
Но вы можете сделать намного лучше, чем это.
Линейный поиск осуществляется в O п время, которое является довольно медленным, хотя это
можете искать любой список, данное ему.
Ваша задача заключается в реализации бинарный поиск, который во время выполнения O из журнала п.
Это довольно быстро.
>> Но есть оговорка.
Двоичного поиска можно только поиск через предварительно отсортированных списков.
Почему это происходит?
Что ж, давайте посмотрим на примере.
Учитывая массив значений, стог сена, мы собираемся искать
иголку, и в этом Например, целое число 3.
>> Таким образом, что бинарный поиск работает так, что мы сравним среднюю стоимость
массив к игле, так же, как, как мы открыли телефонную книгу до середины
страницы в неделю 0.
Таким образом, после сравнения среднее значение для игла, вы можете отказаться от либо
влево или правая половина массива затянув свои границы.
В этом случае, поскольку 3, наша игла, является меньше 10, среднее значение,
Право граница может уменьшаться.
>> Но попытаться сделать ваши границы как можно плотнее.
Если среднее значение не игла, то вы знаете, что вам не нужно, чтобы
включить его в этой категории.
Так ваше право связан может затянуть поиск границы чуть-чуть больше,
не и так далее и так далее, до тех пор, вы нашли иглу.
>> Итак, что же псевдо Код выглядит?
Ну, в то время как мы все еще просматривая список и до сих пор
элементы, чтобы смотреть в, мы берем середину из списка и сравнить, что
среднее значение для нашей иглы.
Если они равны, то это означает, что мы в нашла иголку, и мы можем
вернуться верно.
>> В противном случае, если игла меньше среднее значение, то, что означает, что мы
можно отбросить правую половину и просто поиск по левую сторону массива.
В противном случае, мы будем искать Правая часть массива.
И в конце, если вы не имеете любые больше элементов слева поиск, но вы
Ничего не нашли иглу еще, то вы вернуться ложным.
Поскольку игла определенно не в сена.
>> Теперь один аккуратный вещь об этом псевдо код в бинарный поиск в том, что он может
интерпретироваться как либо итеративный или рекурсивная реализация.
Поэтому было бы рекурсивным, если вы назвали функция поиска в поиске
функционировать по обе половины массива.
Мы рассмотрим рекурсии немного позже в ходе.
Но точно знаю, что это вариант если вы хотели бы попробовать.