wiki

Основные алгоритмы поиска в C¶

Поиск - это фундаментальная операция в программировании. Рассмотрим 3 основных алгоритма поиска с реализацией на языке C.

1. Линейный поиск (Linear Search)¶

Самый простой алгоритм, который последовательно проверяет каждый элемент.

Особенности:

• Работает на любых данных (отсортированных и неотсортированных)
• Время работы: O(n) в худшем случае
• Память: O(1)

Реализация:

#include <stdio.h>

int linear_search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // Возвращаем индекс найденного элемента
        }
    }
    return -1;  // Элемент не найден
}

int main() {
    int data[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    int target = 9;
    
    int result = linear_search(data, size, target);
    
    if (result != -1) {
        printf("Элемент найден на позиции: %d\n", result);
    } else {
        printf("Элемент не найден\n");
    }
    
    return 0;
}

2. Бинарный поиск (Binary Search)¶

Эффективный алгоритм для поиска в отсортированных массивах.

Особенности:

• Работает только на отсортированных данных
• Время работы: O(log n)
• Память: O(1) для итеративной реализации

Реализация (итеративный вариант):

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    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;  // Элемент не найден
}

int main() {
    int data[] = {1, 3, 5, 7, 9, 11, 13};
    int size = sizeof(data) / sizeof(data[0]);
    int target = 7;
    
    int result = binary_search(data, size, target);
    
    if (result != -1) {
        printf("Элемент найден на позиции: %d\n", result);
    } else {
        printf("Элемент не найден\n");
    }
    
    return 0;
}

3. Интерполяционный поиск (Interpolation Search)¶

Улучшенная версия бинарного поиска для равномерно распределенных данных.

Особенности:

• Лучше бинарного поиска для равномерных данных
• Среднее время работы: O(log log n)
• В худшем случае: O(n)

Реализация:

#include <stdio.h>

int interpolation_search(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        if (low == high) {
            if (arr[low] == target) return low;
            return -1;
        }
        
        // Формула интерполяции
        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 data[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int size = sizeof(data) / sizeof(data[0]);
    int target = 50;
    
    int result = interpolation_search(data, size, target);
    
    if (result != -1) {
        printf("Элемент найден на позиции: %d\n", result);
    } else {
        printf("Элемент не найден\n");
    }
    
    return 0;
}

Сравнение алгоритмов поиска¶

Когда какой алгоритм использовать?¶

1. Линейный поиск - когда данные не отсортированы или их мало
2. Бинарный поиск - для отсортированных данных (универсальный выбор)
3. Интерполяционный поиск - для больших, равномерно распределенных данных