Бинарный поиск. Помогите найти ошибку Опции

[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 - 6.11.2006 23:30

[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....
мне просто не с чем было кофе утром пить вот и "закусил" твоей программой..

Сообщение отредактировано: volvo - 6.11.2006 23:31