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


Добавил:DMT
Дата создания:23 апреля 2008, 21:44
Дата обновления:23 апреля 2008, 21:46
Просмотров:6484 последний вчера, 9:54
Комментариев: 0

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

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

Алгоритм двоичного поиска имеет сложность по времени , где 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 дней.

up