Задачи модуля "Поиск": от бинарного поиска до Бойера-Мура

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

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

int binary_search(int A[], int N, int key) {
    int lo = 0;
    int hi = N - 1;
    
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // Защита от переполнения
        
        if (A[mid] == key) {
            return mid; // Элемент найден
        }
        if (A[mid] < key) {
            lo = mid + 1; // Ищем в правой половине
        } else {
            hi = mid - 1; // Ищем в левой половине
        }
    }
    
    return -1; // Элемент не найден
}

Воспользуйтесь основным свойством BST: если искомое значение меньше значения в корне, оно может быть только в левом поддереве. Если больше - только в правом.

Рекурсивный поиск в BST очень похож на бинарный поиск в массиве. Базовый случай - если мы дошли до пустого узла (возвращаем NULL) или нашли узел с нужным значением. Иначе мы рекурсивно вызываем функцию либо для левого, либо для правого сына.

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* searchBST(struct TreeNode* root, int val) {
    // Базовый случай: корень пуст или ключ найден
    if (root == NULL || root->val == val) {
        return root;
    }
    
    // Ключ больше, чем ключ корня → ищем в правом поддереве
    if (root->val < val) {
        return searchBST(root->right, val);
    }
    
    // Ключ меньше → ищем в левом поддереве
    return searchBST(root->left, val);
}

Для реализации эвристики "плохого символа" вам потребуется заранее составить таблицу сдвигов для всех возможных символов алфавита. По умолчанию сдвиг равен длине образца.

Если алфавит состоит из 256 символов (расширенный ASCII), создайте массив badChar[256]. Пройдитесь по всем символам образца, кроме последнего, и запишите для каждого из них сдвиг: badChar[(unsigned char)pat[i]] = m - 1 - i.

Основной цикл: сравнивайте строку и образец справа налево. Если найдено несовпадение, сдвигайте шаблон вправо на значение из badChar для символа текста, который оказался напротив последнего символа образца.

Алгоритм Бойера-Мура-Хорспула работает быстрее наивного поиска за счет того, что при несовпадении символов он может "перепрыгнуть" сразу несколько символов в тексте.

Таблица сдвигов указывает, на сколько позиций можно безопасно сдвинуть образец вправо, если произошла ошибка. Величину сдвига задает не тот символ, на котором сорвалось сравнение, а последний символ окна - в коде это txt[shift + m - 1]. Именно на этом месте решение чаще всего и разъезжается. Возьмем текст ABRACADABRA и образец CADA: буквы B и R в образец не входят и дают прыжок на всю его длину, а C, A и D стоят в таблице со своими расстояниями до конца.

#include <string.h>

#define ALPHABET_SIZE 256

int search_bmh(const char *txt, const char *pat) {
    int m = strlen(pat);
    int n = strlen(txt);
    
    if (m == 0) return 0;
    if (m > n) return -1;
    
    int badChar[ALPHABET_SIZE];
    
    // 1. Заполняем таблицу сдвигов максимальным значением (длиной образца)
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        badChar[i] = m;
    }
    
    // 2. Рассчитываем сдвиги для символов образца (кроме последнего)
    for (int i = 0; i < m - 1; i++) {
        badChar[(unsigned char)pat[i]] = m - 1 - i;
    }
    
    // 3. Поиск
    int shift = 0;
    while (shift <= (n - m)) {
        int j = m - 1;
        
        // Сравниваем символы справа налево
        while (j >= 0 && pat[j] == txt[shift + j]) {
            j--;
        }
        
        if (j < 0) {
            return shift; // Найдено!
        } else {
            // Эвристика плохого символа
            shift += badChar[(unsigned char)txt[shift + m - 1]];
        }
    }
    
    return -1; // Не найдено
}