Поиск: линейный и бинарный
Два способа поиска
- Поиск означает нахождение того, где находится значение в массиве (или утверждение об отсутствии).
- Линейный поиск проверяет каждый элемент по очереди. Работает с любым массивом.
- Бинарный поиск намного быстрее, но требует предварительной сортировки массива.
Линейный поиск
- Пройдите от индекса
0доn - 1, сравнивая каждый элемент с целевым. - Верните индекс, как только вы его найдёте. Если дошли до конца, верните
-1. - Для массива из
nэлементов здесь рассматривается доnиз них.
Почему сортировка необходима для бинарного поиска
- Если массив отсортирован, можно перейти к середине и сравнить.
- Если середина меньше, целевое значение должно быть в правой половине; если больше — в левой.
- Каждый шаг отбрасывает половину массива, поэтому это очень быстро (около
log2(n)шагов).
low, high, mid
- Удерживайте две границы:
low(начало) иhigh(конец). Середина определяется какmid = low + (high - low) / 2. - Если
a[mid]является целевым значением, вернитеmid. Еслиa[mid] < target, переместитеlow = mid + 1; иначеhigh = mid - 1. - Остановитесь, если
low > high— целевое значение отсутствует, тогда верните-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
Распространенные ошибки
- Бинарному поиску нужен отсортированный массив.
- Линейный поиск проверяет каждый элемент последовательно.
Теперь попробуйте сами
- Для бинарного поиска предполагается, что массив уже отсортирован. Используйте
low,highиmid. - Возвращайте
-1, если значение не найдено. Не пишите код дляmain— чекер предоставляет его сам.
Линейный против бинарного поиска
Бинарный поиск на каждом шаге уменьшает диапазон пополам.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните int linear_search(const int a[], int n, int target) так, чтобы он возвращал индекс первого ⟨target⟩, или -1, если его нет в массиве. Не пишите ни main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните int binary_search(const int a[], int n, int target) для отсортированного массива. Верните индекс ⟨target⟩, или -1. Используйте low, high и mid. Не пишите ни main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните int first_negative(const int a[], int n) так, чтобы он возвращал индекс первого элемента меньше 0, или -1, если такого нет. Не пишите ни main.
Нажмите Запустить, чтобы увидеть результат здесь.