[Музыка играет] 

ZAMYLA Чан: Первое, что вы могли бы уведомление о находке является то, что мы уже уже код, написанный для нас. Это называется код распределение. Таким образом, мы не только написание собственного код с нуля больше. Скорее, мы заполнения пустот в некотором предварительно существующего кода. 

Программа find.c запрашивает номера заполнить стог сена, поиск стоге сена для пользователей представленных иглы, и он делает это путем вызова рода и поиска, функции, определенные в helpers.c. Так find.c написано уже. Ваша задача написать помощников. 

Так что мы делаем? Мы реализации две функции. Поиск, который возвращает истину, если значение находится в стоге сена, возвращаясь ложным, если значение не в стоге сена. А потом мы также осуществляет рода которая сортирует массив с именем значения. 

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

Но есть оговорка. Двоичного поиска можно только поиск через предварительно отсортированных списков. Почему это происходит? 

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

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

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

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

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

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

И это возможно, потому что массивы передаются по ссылке в С. Теперь мы см. об этом чуть позже, но Существенное различие между передачей в чем-то вроде целое и прохождения в массиве, в том, что, когда вы перейти в целое число, C только собирается сделать копию этого целого и передать его функции. Оригинальный переменная не будет изменена После того, как функция закончена. С массива, с другой стороны, это не собирается делать копию, и вы будете фактически редактирования Сам очень массив. 

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

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

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

Итак, это два примера рода алгоритмы, которые можно реализовать для программа находка. Как только вы закончите рода, и у тебя сделано поиска, вы закончите. Меня зовут Zamyla, и это CS50. 

[Музыка играет]