Этот алгоритм является более быстрым, чем линейный, но применяетсятолько к упорядоченным массивам. Время дихотомического поиска пропорционально величине log2n, где n — количество элементов таблицы эталонов. Таким образом, ускорение достигается за счет дополнительной информации о расположении элементов, а верхняя оценка алгоритма О(n) = log2n.
Метод основан на последовательном делении на 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 Поиск ключа");
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);
}
Тема 2.2. Алгоритмы обработки данных линейной структуры
АЛГОРИТМЫ СОРТИРОВКИ
