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

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

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

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

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

2. Повторять

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

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

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

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

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

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

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

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],

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

2. 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.println("\n Поиск ключа");

int lev, prav, k;

boolean naideno;

do{

int arg,num;

System.out.println("\n Введите аргумент поиска – искомый ключ");

arg=sc.nextInt();

if (arg>=0){

num=-1;

if arg==key[n-1] {

k=n-1;

naideno=true;

}

else {

naideno=false;

do {

k=(int)((lev+prav)/2);

if (arg==key[k])

naideno=true;

else

if (arg>key[k])

lev= k;

else

prav= k;

} while (naideno || (lev==prav-1));

}

if (naideno)

System.out.println("Ключ найден, его номер "+ k);

else

System.out.println("Такого ключа нет");

} while (arg>=0);

}