Алгоритмы поиска

Линейный поиск (linear search)

Бинарный поиск (binar search)

Линейный поиск

Алгоритм линейного поиска оптимально подходит для неотсортированных массивов. Работа алгоритма заключается в переборе всех элементом массива и сравнении их с ключем.

int Search(int* arr, const int size, int key)
{
    int iKey = -1;
    int i = 0;
    for (i = 0; i < size; i++) {
        if (arr[i] == key) {
            iKey = i;
            break;
        }
    }
    return iKey;
}

Вы можете увидеть работу алгоритма визуально в режиме реального времени! Для этого клонируйте проект в Visual Studio и запустите:

https://github.com/SergeyDeleu/Visual_SearchAlgorithm.git

Бинарный поиск

Бинарный поиск работает только с отсортированными массивами! Алгоритм бинарного поиска работает следующим образом:

1. Выбирается элемент посередине массива. Если этот элемент равен ключу, то поиск прекращается.
2. Если элемент меньше ключа, то поиск продолжается в правой части по такому же алгоритму.
3. Если элемент больше ключа, то поиск продолжается в левой части аналогично.

Реализация алгоритма поиска на С++:

void BinarSearch(int* arr, const int size, int key) {
    bool flag = false;
    int l = 0; // левая граница
    int r = size-1; // правая граница
    int mid;
    while ((l <= r) && (flag != true)) {
                // считываем срединный индекс отрезка [l,r]
        mid = (l + r) / 2; 
                //проверяем ключ со серединным элементом
        if (arr[mid] == key) flag = true;
                // проверяем, какую часть нужно отбросить
        if (arr[mid] > key) r = mid - 1; 
        else l = mid + 1;
    }
    if (flag) cout << "iKey = " << mid << endl;
    else cout << "No this element in massive!" << endl;
}

Вы можете увидеть работу алгоритма визуально в режиме реального времени! Для этого клонируйте проект в Visual Studio и запустите:

https://github.com/SergeyDeleu/VisualTestingAlgorithm.git