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

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

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

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

Но есть оговорка. Двоичного поиска можно только поиск через предварительно отсортированных списков. Почему это происходит? Что ж, давайте посмотрим на примере. Учитывая массив значений, стог сена, мы собираемся искать иголку, и в этом Например, целое число 3. 

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

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

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

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

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