Линейный поиск (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
Бинарный поиск
Бинарный поиск работает только с отсортированными массивами! Алгоритм бинарного поиска работает следующим образом:
- Выбирается элемент посередине массива. Если этот элемент равен ключу, то поиск прекращается.
- Если элемент меньше ключа, то поиск продолжается в правой части по такому же алгоритму.
- Если элемент больше ключа, то поиск продолжается в левой части аналогично.
Реализация алгоритма поиска на С++:
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