Для эффективного поиска в отсортированном массиве можно применить алгоритм
двоичного поиска Cедующая подпрограмма, возвращает индекс элемента в массиве
Код на 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); }
Алгоритм двоичного поиска имеет сложность по времени , где
n – число элементов отсортированного массива. Для
сравнения скорости линейного поиска со скоростью двоичного поиска приведем
следующую таблицу (табл. 2.1), которая будет полезна и в других случаях:
Таблица 2.1
Сравнение порядков сложности алгоритмов
n |

|

|

|

|
1 |
0 |
0 |
1 |
1 |
16 |
4 |
64 |
32 |
256 |
256 |
8 |
2048 |
1024 |
65536 |
4096 |
12 |
49152 |
32768 |
16777216 |
65536 |
16 |
1048565 |
1048476 |
4294967296 |
1048476 |
20 |
20969520 |
33554432 |
1099301922576 |
Эта таблица показывает, что если алгоритм, имеющий сложность реализуется за 20 микросекунд, то алгоритм, имеющий сложность
– за 1 секунду, – за
33 секунды, а – за 12
дней.
|