Поиск
Поиск — это процесс определения, существует ли конкретный элемент и какова его точная позиция в наборе данных. Это фундаментальная операция, используемая почти во всех программах.
Сравнение трёх алгоритмов поиска
Линейный поиск O(n)
Не требует отсортированных данных
Сравнение по одному, просто и надёжно
Подходит для: небольших или неупорядоченных наборов данных
Бинарный поиск O(log n)
Требует отсортированных данных
Каждый раз делит диапазон пополам, исключая половину
Подходит для: универсальное решение для отсортированных данных
Интерполяционный поиск O(log log n)
Требует отсортированного порядка + равномерного распределения
Оценивает позицию на основе пропорции значения
Подходит для: оптимально, когда данные равномерно распределены
Линейный поиск
Сравнивает по одному, начиная с первого элемента, пока не будет найден целевой элемент или пока список не будет исчерпан. Не требует сортировки данных. Временная сложность O(n).
Бинарный поиск
Требует, чтобы данные были отсортированы. Каждый раз сравнивает со средним элементом, уменьшая диапазон поиска вдвое. Временная сложность O(log n).
Интерполяционный поиск
Оптимизация бинарного поиска. Вместо выбора средней точки она оценивает возможную позицию на основе искомого значения. Когда данные распределены равномерно, она может достигать O(log log n).
Пример
/* Линейный поиск: O(n), не требует отсортированного порядка */
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}
/* Бинарный поиск: O(log n), требует, чтобы массив был отсортирован (по возрастанию) */
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2; /* Вычисление, предотвращающее переполнение */
if (arr[mid] == target) return mid; /* Найдено */
if (arr[mid] < target)
left = mid + 1; /* Искомое значение находится в правой половине */
else
right = mid - 1; /* Искомое значение находится в левой половине */
}
return -1; /* Не найдено */
}
/* Интерполяционный поиск: в среднем O(log log n), требует равномерно распределённых данных */
int interpolationSearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
/* Формула интерполяции: оценка позиции на основе пропорциональной величины значения */
int pos = low + ((target - arr[low]) * (high - low))
/ (arr[high] - arr[low]);
if (arr[pos] == target) return pos;
if (arr[pos] < target)
low = pos + 1;
else
high = pos - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = 9;
printf("Линейный поиск 50: индекс %d\n", linearSearch(arr, n, 50)); /* Вывод: 4 */
printf("Бинарный поиск 50: индекс %d\n", binarySearch(arr, 0, n-1, 50)); /* Вывод: 4 */
printf("Интерполяционный поиск 50: индекс %d\n", interpolationSearch(arr, n, 50)); /* Вывод: 4 */
return 0;
}
Сводка сравнения сложности
| Алгоритм | Временная сложность | Требуется сортировка | Применимые сценарии |
|---|---|---|---|
| Линейный поиск | O(n) | нет | Малый объём данных или неотсортированные данные |
| Бинарный поиск | O(log n) | Да | Отсортированные массивы, общие и эффективные |
| Интерполяционный поиск | O(log log n)Средний случай | Да | Конкретные сценарии с равномерно распределёнными данными |