Нужен пример бинарного поиска - Turbo Pascal
Формулировка задачи:
Бинарный поиск
Решение задачи: «Нужен пример бинарного поиска»
textual
Листинг программы
function BinSearch(n: Integer; const a: array of Integer; Size: Integer): Integer; var l, r, m: Integer; begin l:=0; r:=Size-1; while l<=r do begin m:=l+(r-l) div 2; if a[m]>=n then r:=m-1 else l:=m+1; end; BinSearch:=l; end; const n=10; var a: array [1..n] of Integer; i, k: Integer; begin Randomize; for i:=1 to n do a[i]:=i*2; k:=Random(22); i:=BinSearch(k,a,n)+1; Write('Число ',k); if a[i]<>k then WriteLn(' не найдено.') else WriteLn(' найдено в позиции ',i,'.'); end.
Объяснение кода листинга программы
- В функции BinSearch объявлены три переменные: l, r и m. Они представляют собой указатели на элементы массива a. Переменная l и r инициализируются как 0 и Size-1 соответственно, где Size - это размер массива.
- Затем в цикле while выполняются следующие действия:
- m устанавливается как среднее значение между l и r. Это позволяет найти средний элемент массива при каждом проходе цикла.
- Если значение a[m] больше или равно n, то это означает, что число n не найдено в массиве. В этом случае значение переменной r устанавливается равным m-1, что означает, что поиск продолжается в левой части массива.
- Если значение a[m] меньше n, то это означает, что число n найдено в массиве. В этом случае значение переменной l устанавливается равным m+1, что означает, что поиск продолжается в правой части массива.
- После завершения цикла while значение переменной BinSearch устанавливается равным l, что является позицией, в которой найдено число n.
- В основной части программы объявляется переменная n, которая равна 10.
- Затем создается массив a, который содержит 10 чисел, каждое из которых удваивается.
- Выбирается случайное число k из диапазона от 1 до 22.
- Вызывается функция BinSearch с аргументами k, a и n. Результат поиска (позиция k в массиве) сохраняется в переменной i.
- Выводится сообщение о том, что число k найдено или не найдено в соответствующей позиции.
- Конец программы.