Главная страница
Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Алгоритм бінарного пошуку в упорядкованому масиві
- Ввести розмір масиву.
- Ввести елементи масиву та ключ пошуку.
- Покласти ліву межу масиву рівною одиниці, праву межу — рівною введеній кількості елементів.
3.1. Якщо ліва межа масиву більше правої, то завершити пошук, вважаючи його безрезультатним, інакше виконати дії, зазначені в пунктах 3.2-3.4. 3.2. Визначити індекс середнього елемента за наведеною нижче формулою middle = (left + right) div 2. 3.3. Порівняти ключ пошуку зі значенням середнього елемента. Якщо ці значення збігаються, то завершити пошук, вважаючи його успішним, інакше визначити підмасив, в якому треба продовжити пошук. Для цього перейти до пункту 3.4. 3.4. Якщо ключ пошуку менше значення середнього елемента, виконати процедуру бінарного пошуку для лівого підмасиву з межами left та middle-1, інакше виконати процедуру бінарного пошуку для правого підмасиву з межами middle+1 та right. - Якщо пошук завершено успішно, вивести знайдений елемент та його індекс, інакше вивести повідомлення про безуспішність пошуку.
Цей алгоритм реалізовано програмою ех7_6. Результати роботи програми зображено на рис. 7.5.
Program EX7_6; var mas: array [1..15] of integer; i, n: integer; flag: boolean; x: integer; middle: integer; procedure BinSearch(left, right: integer); begin if left> right then flag: =false else begin middle: =(left+right) div 2; if x< mas[middle] then flag: =true else if x< mas[middle] then Binsearch(left, middle-1) else binsearch(middle+1, right); end; end; begin writeln('binary search'); writeln('enter number of components'); readln(n); writeln('enter array'); for i: =1 to n do read(mas[i]); writeln('enter value to search'); readln(x); binsearch(1, n); if flag then writeln('item=', middle) else writeln('value not found'); end.

Рис. 7.5. Результати роботи програми ех7_6. Бінарний пошук в упорядкованому масиві
Демонстрація прикладу
|