Помощь - Поиск - Пользователи - Календарь
Полная версия: Бинарный поиск. Помогите найти ошибку
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
scre@m
Помогите найти ошибку. Нужно сгенерировать массив, отсортировать его, а затем бинарным поиском найти заданное число a. Все сделал, но результат поиска всегда один и тот же - "такого нет". Что не так?

program x3;
uses crt;
const n=20;
var m: array [1..n] of integer;
found: boolean;
a,i,fst,lst: integer;
k,j: integer;
begin
clrscr;
randomize;
begin
for i:=1 to n do
m[i]:=random(20);
for i:=1 to n do
write(m[i],' ');
readln;
begin
for i:=2 to n do
for j:=n downto i do
if m[j-1]<m[j] then begin
k:=m[j]; m[j]:=m[j-1];
m[j-1]:=k;
end;
end;
end;
write('otsortirovan:');readln;
for i:=1 to n do
write(m[i],' ');
readln;
writeln('vvedite chislo ot 0 do 20'); readln(a);
begin
fst:=1; lst:=n; found:=false;
repeat
i:=(fst+lst) div 2;
if m[i]=a then found:=true
else if m[i]<a then fst:=i+i
else lst:=i-1
until(found) or (fst>lst); end;
if found=true then writeln ('nomer iskomogo elementa',i)
else writeln('takogo net');
readln;
end.


Про теги не забывай
volvo
Обязательно велосипед изобрести?
Выкладывали ведь уже: Бинарный (двоичный) поиск
Altair
uses
crt;
const
n=19;
type
telem = integer;
arrtype= array[0..n] of telem;
var
m: arrtype;
found: boolean;
k,j,a_search,i,fst,lst: integer;
begin
{ инициализация ... }
randomize;
for i:=0 to n do begin
m[i]:=random(20);
write(m[i],' ')
end;
writeln(chr(10)+chr(13)+'press enter...');
readln;
{ сортировка пузырьком ...}
for i:=0 to n-1 do
for j:=i+1 to n do
if m[j-1]>m[j] then begin {знак!!!}
k:=m[j];
m[j]:=m[j-1];
m[j-1]:=k;
end;
write('Sort: ');
for i:=0 to n do write(m[i],' '); writeln;
writeln('Enter number ');
readln(a_search);
{ поиск ... }
fst:=0; lst:=n; found:=false;
repeat
i:=(fst+lst) div 2;
if (m[i]=a_search) then
found:=true
else begin
if (m[i] < a_search) then
fst:=i+1 {ВНИМАНИЕ ЗДЕСЬ БЫЛА ОШИБКА i вместо 1 !!!}
else
lst:=i-1
end;
until (found=true) or (fst>lst);
if (found=true) then
writeln ('number = ',i+1) {+1 потому что массив от 0 у нас...}
else writeln('Not found!');
readln;
end.

У тебя были ошибки в программе. Самая главная - i вместо 1.

(добавил позже)
p.s. у предыдущей программы проблеммы с сортировкой, я немного изменил программу, разбив ее логически на процедуры.
Так она нагляднее и легче сопровождается.
uses
crt;
const
n=20;
type
telem = integer;
arrtype= array[1..n] of telem;

Procedure Bubble(Var ar: arrType; n: integer);
Var
i, j, T: Integer;
Begin
For i := 1 To n Do
For j := n DownTo i+1 Do
If ar[Pred(j)] > ar[j] Then { < }
Begin
T := ar[Pred(j)]; ar[Pred(j)] := ar[j]; ar[j] := T
End
End;

Function Bin_Search (m:arrtype; n:integer; a_search: telem) : integer;
var
i,fst,lst : integer;
found : boolean;
begin
fst:=0; lst:=n; found:=false;
repeat
i:=(fst+lst) div 2;
if (m[i]=a_search) then
found:=true
else begin
if (m[i] < a_search) then
fst:=i+1 {ВНИМАНИЕ ЗДЕСЬ БЫЛА ОШИБКА i вместо 1 !!!}
else
lst:=i-1
end;
until (found=true) or (fst>lst);
if (found = true) then bin_search := i+1 else bin_search := -1;
end;

procedure print_arr(a:arrtype; n:integer);
var
i:integer;
begin
for i:=1 to n do write(a[i],' '); writeln
end;

procedure init_arr (var a:arrtype; n:integer);
var
i:integer;
begin
randomize;
for i:=1 to n do a[i]:=random(20);
end;

var
m: arrtype;
result,a_search,i: integer;

begin
init_arr(m,n);
print_arr(m,n);

writeln(chr(10)+chr(13)+'press enter...');
readln;

bubble(m,n);

write('Sort: ');
print_arr(m,n);

writeln('Enter number ');
readln(a_search);
{ поиск ... }

result:=bin_search(m,n,a_search);

if (result > 0) then
writeln ('number = ',result)
else writeln('Not found!');
readln;
end.

p.s. а вообще Вольво прав, используй FAQ....
мне просто не с чем было кофе утром пить вот и "закусил" твоей программой..
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.