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

В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n<k=2^m.

Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Так как массив упорядочен, то, если a[S]<X – искомый элемент находится в правой части массива, иначе – находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.

L S R

int b;

cout << "\ nB =?"; cin >> b;

int l = 0, r = n-1, s;

do

{

s = (l + r) / 2;/ / середній елемент

if (a [s] <b) l = s +1;/ / перенести леую кордон

else r = s;/ / перенести праву межу

} while (l! = r);

if (a [l] == b) return l;

else return -1;

...

Постановка завдання

Завдання 10.1.

Сформувати масив з n елементів за допомогою датчика випадкових чисел (n задається користувачем з клавіатури).

Роздрукувати отриманий масив.

Виконати видалення зазначених елементів з масиву.

Вивести отриманий результат.

Виконати додавання зазначених елементів в масив.

Вивести отриманий результат.

Виконати перестановку елементів у масиві.

Вивести отриманий результат.

Виконати пошук вказаних в масиві елементів і підрахувати кількість порівнянь, необхідних для пошуку потрібного елемента.

Вивести отриманий результат.

Виконати сортування масиву зазначеним методом.

Вивести отриманий результат.

Виконати пошук вказаних елементів у відсортованому масиві і підрахувати кількість порівнянь, необхідних для пошуку потрібного елемента.

Вивести отриманий результат.