Бинарный (двоичный) поиск, только для отсортированного массива Опции

[klem4]

value - искомое значение
right и left - сдвигающиеся границы массива.

Код

procedure bin_s;
var
  value:integer{array type};
  x:array[1..n] of integer;
  i,nn,nfind,right,left:integer;
begin
  writeln('value=');readln(value);
  left:=1;
  right:=n;
  while ((right-left)>1) do
   begin
      nn:=(right+left) div 2;
      if value<=x[nn] then
       right:=nn
        else left:=nn;
   end;
   if value=x[left] then
    nfind:=left
     else if value=x[right] then
      nfind:=right;
  writeln('nfind=',nfind);
  readln;
end;

Скорость :
1000 элементов - 10 итераций цикла.

Процедура не срабатывает с такими исходными данными (возвращается результат "nfind = 2"):

const
  n = 20;
  x: array[1 .. n] of integer =
    ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
     43, 44, 49, 50, 59, 60, 63, 73, 77, 85);
  { Значение для поиска: value = 34 }

Volvo

[klem4]

НЕ знаю почему, я с этим уже сталкивался и объяснить не могу, но вот так работает :

Код

const n = 20;

const
x: array[1 .. n] of integer =
  ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
   43, 44, 49, 50, 59, 60, 63, 73, 77, 85);

{ задай для поиска value = 34 }

procedure bin_s;
var
value:integer{array type};
 { тут не надо объявлять массив ! ! !}
i,nn,nfind,right,left:integer;
begin
writeln('value=');readln(value);
left:=1;
right:=n;
while ((right-left)>1) do
  begin
    nn:=(right+left) div 2;
    if value<=x[nn] then
      right:=nn
    else left:=nn;
  end;

if value=x[left] then
  nfind:=left
else if value=x[right] then
       nfind:=right;
writeln('nfind=',nfind);
readln;
end;

var i: integer;
begin
for i := 1 to n do
  write(x[i]:4);
writeln;

bin_s
end.

Теперь все просто отлично работает, но почему!!!!?? не работало до этого ??
ИМХО это баги паскаля, связанные с глобальными и локальными переменными...

Сообщение отредактировано: klem4 - 25.02.2005 8:12

[volvo]

ИМХО это баги паскаля, связанные с глобальными и локальными переменными...

Это не баги паскаля, а неверное проектирование... У тебя же процедура для поиска, так что, для того, чтобы ей воспользоваться я должен залезть вовнутрь и изменить ее содержимое? Ты изначально должен был расположить массив за пределами процедуры...

Кстати, еще вопрос:
Допустим, у тебя 3 массива: X, X1, X2.

Код

Var x, x1, x2: array[1 .. n] Of integer;
Procedure bin_s;
Begin ... End;

{ Вот тут тебе надо найти номер элемента из массива X1 }
...
{ тут - элемента из массива X2 }
...
{ а вот тут - номер элемента из массива X }

Твои действия?

Или еще более коварный вариант - если все 3 массива имеют разную размерность...

[klem4]

Вот :low:

Код

uses crt;
const n=15;
type mass=array[1..n] of integer;
var x:mass;
   i:integer;
function bin_s(x:mass):integer;
var right,left:integer;
   nn,value:integer;
   nfind:integer;
begin
  write('Value=');readln(value);
  left:=1;
  right:=n;
  while (right-left>1) do
   begin
      nn:=(right+left) div 2;
      if value>x[nn] then
       left:=nn
        else right:=nn;
   end;
   if x[left]=value then
    nfind:=left
     else if x[right]=value then
      nfind:=right
       else nfind:=0;
   writeln;
   writeln('Nfind=',nfind);
end;
Begin
  for i:=1 to n do
   readln(x[i]);
  bin_s(x);
  readln;
end.

[volvo]

Или еще более коварный вариант - если все 3 массива имеют разную размерность...

Я так понимаю, этот вариант не рассматривался?

[klem4]

Щас сделаем ...

[klem4]

Не могу найти ошибку

Код

uses crt;
type

  arrT=array[1..1000] of integer;

var
   x:arrT;
   y:arrT;
   z:arrT;
   i:integer;
   m,n:integer;

function f(z:arrT;p:integer):integer;
var
  value:integer;
  left,right:integer;
  nn:integer;
  nfind:integer;
begin
 write('Value=');readln(value);
 left:=1;
 right:=p;
 while (right-left>1) do
  begin
     nn:=(right+left) div 2;
     if value>z[nn] then
      left:=nn
       else right:=nn;
  end;
  if z[left]=value then
   nfind:=left
    else if z[right]=value then
     nfind:=right
      else nfind:=0;
  writeln;
  writeln('Nfind=',nfind);
end;
Begin
  clrscr;
  write('n=');
  readln(n);
  for i:=1 to n do
   readln(x[i]);
  writeln;
  f(x,n);
  readln;
end.

[volvo]

А в чем, собственно, ошибка? Эта программа отрабатывает.

[klem4]

например 1,2,3,0,5 если искать 0 то возвращает nfind=0.
Или тока у меня ??))

[volvo]

А как же упорядоченность? "Бинарный (двоичный) поиск, только для отсортированного массива"... Массив <1, 2, 3, 0, 5> не является отсортированным

[klem4]

так точно!) ну значит теперь все в поряде

[volvo]

ну значит теперь все в поряде

Правда? А у меня еще несколько вопросов...
1. Описана функция... А что, собственно, она возвращает?
2. При работе с бОльшими массивами - проблемы... Попробуй, например, описать вот так:

Код

type
 arrT=array[1..10000] of integer;

и запустить программу. Что произойдет? А ведь этот метод по определению желательно использовать для больших объемов данных... Так что еще не все..

[volvo]

Проверь вот это:

Код

Type
 TType = Integer;

Function bin_search(Var x: Array Of TType;
        Const n: Integer; Value: TType): Integer;
Var
 nn, nFind, Right, Left: Integer;
Begin
 Left := 0; Right := Pred(n);
 While (Right - Left) > 1 Do
   Begin
     nn := (Right + Left) div 2;
     If Value <= x[nn] Then Right := nn
     Else Left := nn
   End;

 If Value = x[Left] Then nFind := Left
 Else
   If Value = x[Right] Then nFind := Right
   Else nFind := -2;

 bin_search := nFind + 1;
End;


Const
 n_1 = 20;
 x: array[1 .. n_1] of TType =
   ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
    43, 44, 49, 50, 59, 60, 63, 73, 77, 85);

 n_2 = 25;
 x1: array[1 .. n_2] of TType =
   ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
    43, 44, 49, 50, 59, 60, 63, 73, 77, 85,
    86, 87, 88, 89, 90);

 n_3 = 30;
 x2: array[1 .. n_3] of TType =
   ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
    43, 44, 49, 50, 59, 60, 63, 73, 77, 85,
    86, 87, 88, 89, 90, 91, 92, 93, 94, 95);

var
 i: integer;

begin
 writeln( bin_search(x, n_1, 18) );
 writeln( bin_search(x1, n_2, 38) );
 writeln( bin_search(x2, n_3, 94) );
end.