Алгоритм дихотомического поиска

Этот алгоритм является более быстрым, чем линейный, но применяетсятолько к упорядоченным массивам. Время дихотомического поиска пропорционально величине log₂n, где n — количество элементов таблицы эталонов. Таким образом, ускорение достигается за счет дополнительной информации о расположении элементов, а верхняя оценка алгоритма О(n) = log₂n.

Метод основан на последовательном делении на 2 диапазона поиска. При этом на каждом шаге либо находится элемент, либо происходит переход в одну из половин диапазона. В процессе поиска выполняется не только сравнение на равенство, но и на больше-меньше. Последняя операция позволяет выбрать очередную половину диапазона таблицы. Если массив эталонов не упорядочен, то выбор будет сделан неверно, и результат можно не получить никогда (говорят, что алгоритм расходится).

Общийалгоритм поиска будет таким же, как в п. 1.

1. Ввести исходный массив (ключей).

2. Повторять

ввести аргумент поиска и вывести результат

пока не надоест.

3. Закончить.

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

Уточненный алгоритм можно представить в следующем виде.

1.1. Ввести количество элементов массива (n).

1.2. Инициировать датчик случайных чисел.

1.3. Для номера ключа (i) от 0 до n

1.3.1. Вычислить ключ[i].

2. Упорядочить ключи по возрастанию:

2.1. Для номера просмотра (k) от 1 до n - 1

2.1.1. Для номера слова (i) от 0 до n - k

Если ключ [i] > ключ [i+1],

поменять местами ключ[i] и ключ[i+1].

3. Выполнять

3. 1. Ввести аргумент поиска (целое число);

3. 2. Если аргумент поиска больше или равен нулю,

3.2.1 Граница_левая (диапазона поиска) = 0;

3.2.2. Граница_правая (диапазона поиска) = n - 1 (Длина.массива – 1);

3.2.3. Если аргумент поиска = ключ [n - 1],

a) Признак = «Найдено»;

b) Номер ключа k = n – 1.

Иначе

3.2.4. Признак = «Не найдено».

3.2.5. Выполнять

a) k = Целое ((Граница_левая + Граница_правая)/2);

b) Если аргумент поиска = ключ [k],

Признак:= «Найдено»

Иначе

Если аргумент поиска > ключ [k],

Граница_левая = k

Иначе

Граница_правая = k.

Пока не «Найдено» Или (Граница_левая = Граница_правая - 1).

3.3. Если «Найдено»,

вывести: «Ключ найден под номером k»,

Иначе

вывести: «Такого ключа в массиве нет».

пока будет аргумент поиска больше или равен нулю.

4. Закончить.

В алгоритме пункт 3.2.3 применен для обеспечения нахождения последнего элемента массива. Дело в том, что при целочисленном делении на 2 дробная часть частного отбрасывается, и результат всегда будет на 1 меньше, чем длина таблицы.

Будем использовать те же обозначения переменных, что и для линейного поиска. Значения ключей получим как случайные числа из диапазона от 0 до 99. Фрагмент программы дихотомического поиска, соответствующая приведенному выше алгоритму, будет иметь вид.

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int n;

System.out.print("Введите количество элементов массива => ");

n=sc.nextInt();

System.out.println("\t Элементы массива ");

int key[]=new int[n];

Random rn=new Random();

for (int i = 0; i < key.length;i++) {

key[i]=rn.nextInt(100);

System.out.print(key[i] +” “); }

System.out.println("\n Поиск ключа");