Поиск в отсортированном массиве

Для эффективного поиска в отсортированном массиве можно применить алгоритм двоичного поиска

Код на C++
int search (int *x, int l, int u, int key)
//предполагается, что массив x отсортирован
//ищется x[m] равный key,
//если l<=m<=u, то возвращается m,
//иначе возвращается -1
{	int m=(l+u)/2;
	if (l>u) return -1;
	if (x[m]==key) return m;
	if (key<x[m]) return search(x,l,m,key);
	else return search(x,m,u,key);
}
При использовании обязательна ссылка на http://DMTSoft.ru

Алгоритм двоичного поиска имеет сложность по времени , где n – число элементов отсортированного массива. Для сравнения скорости линейного поиска со скоростью двоичного поиска приведем следующую таблицу (табл. 2.1), которая будет полезна и в других случаях:

Таблица 2.1

Сравнение порядков сложности алгоритмов

Эта таблица показывает, что если алгоритм, имеющий сложность реализуется за 20 микросекунд, то алгоритм, имеющий сложность – за 1 секунду, – за 33 секунды, а – за 12 дней.