Главная | Обратная связь

Теория двоичного поиска.

Предположим, что переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Поиск мы всегда будем начинать с анализа среднего элемента отрезка массива. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M (средний элемент) – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Пример реализации.

#include <iostream>#include <stdlib.h>#include <time.h> using namespace std; int BinarySearch (int A[], int Lb, int Ub, int Key){ int M; while(1){ M = (Lb + Ub)/2; if (Key < A[M]) Ub = M - 1; else if (Key > A[M]) Lb = M + 1; else return M; if (Lb > Ub) return -1; }} void main(){ srand(time(NULL)); const long SIZE=10; int ar[SIZE]; int key,ind; // до сортировки for(int i=0;i<SIZE;i++){ ar[i]=rand()%100; cout<<ar[i]<<"\t"; } cout<<"\n\n"; cout<<"Enter any digit:"; cin>>key; ind=BinarySearch(ar,0,SIZE,key); cout<<"Index - "<<ind<<"\t"; cout<<"\n\n";}

Двоичный поиск - очень мощный метод. Посудите сами: например, длина массива равна 1023, после первого сравнения область сужается до 11 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Предыдущая	Оглавление	Следующая
Предыдущая	Оглавление	Следующая

Домашнее задание

Задача №1.

Написать функцию, которая рекурсивно вычисляет сумму чисел в заданном диапазоне.

Задача №2.

Легенда гласит, что где-то в Ханое находится храм, в котором размещена следующая конструкция: на основании укреплены 3 алмазных стержня, на один из которых при сотворении мира Брахма нанизал 64 золотых диска с отверстием посередине, причем внизу оказался самый большой диск, на нем – чуть меньший и так далее, пока на верхушке пирамиды не оказался самый маленький диск. Жрецы храма обязаны перекладывать диски по следующим правилам:

1. За один ход можно перенести только один диск.

2. Нельзя класть больший диск на меньший.

Руководствуясь этими нехитрыми правилами, жрецы должны перенести исходную пирамиду с 1-го стержня на 3-й. Как только они справятся с этим заданием, наступит конец света.

Мы предлагаем Вам решить данную задачу с помощью рекурсии.

Предыдущая

Оглавление

Следующая

 

 

Предыдущая

Оглавление

Следующая

Урок №12.

• Статическое и динамическое выделение памяти.
• Указатели.
• Указатели и массивы.
• Указатели - аргументы функций. Передача аргументов по указателю.
• Домашнее задание.
• Тест

Предыдущая	Оглавление	Следующая
Предыдущая	Оглавление	Следующая