Searching: linear and binary · Поиск: линейный и бинарный
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
Два способа поиска
- Поиск означает нахождение того, где находится значение в массиве (или утверждение об отсутствии).
- Линейный поиск проверяет каждый элемент по очереди. Работает с любым массивом.
- Бинарный поиск намного быстрее, но требует предварительной сортировки массива.
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
Линейный поиск
- Пройдите от индекса
0доn - 1, сравнивая каждый элемент с целевым. - Верните индекс, как только вы его найдёте. Если дошли до конца, верните
-1. - Для массива из
nэлементов здесь рассматривается доnиз них.
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
Почему сортировка необходима для бинарного поиска
- Если массив отсортирован, можно перейти к середине и сравнить.
- Если середина меньше, целевое значение должно быть в правой половине; если больше — в левой.
- Каждый шаг отбрасывает половину массива, поэтому это очень быстро (около
log2(n)шагов).
low, high, mid
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
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;
}
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
Распространенные ошибки
- Бинарному поиску нужен отсортированный массив.
- Линейный поиск проверяет каждый элемент последовательно.
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
Теперь попробуйте сами
- Для бинарного поиска предполагается, что массив уже отсортирован. Используйте
low,highиmid. - Возвращайте
-1, если значение не найдено. Не пишите код дляmain— чекер предоставляет его сам.
Linear vs binary search · Линейный против бинарного поиска
Binary search halves the range each step. · Бинарный поиск на каждом шаге уменьшает диапазон пополам.
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do not write a main. · Заполните int linear_search(const int a[], int n, int target) так, чтобы он возвращал индекс первого ⟨target⟩, или -1, если его нет в массиве. Не пишите ни main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do not write a main. · Заполните int binary_search(const int a[], int n, int target) для отсортированного массива. Верните индекс ⟨target⟩, или -1. Используйте low, high и mid. Не пишите ни main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do not write a main. · Заполните int first_negative(const int a[], int n) так, чтобы он возвращал индекс первого элемента меньше 0, или -1, если такого нет. Не пишите ни main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.