Версия для печати темы
Форум «Всё о Паскале» _ Задачи _ Бинарный (двоичный) поиск
Автор: klem4 24.02.2005 22:35
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 25.02.2005 12:06
НЕ знаю почему, я с этим уже сталкивался и объяснить не могу, но вот так работает :
Код
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.
Теперь все просто отлично работает, но почему!!!!?? не работало до этого ??
ИМХО это баги паскаля, связанные с глобальными и локальными переменными...
Автор: volvo 25.02.2005 14:41
Цитата(klem4 @ 25.02.05 7:06)
ИМХО это баги паскаля, связанные с глобальными и локальными переменными...
Это не баги паскаля, а неверное проектирование... У тебя же процедура для поиска, так что, для того, чтобы ей воспользоваться я должен залезть вовнутрь и изменить ее содержимое? Ты изначально должен был расположить массив за пределами процедуры...
Кстати, еще вопрос:
Допустим, у тебя 3 массива: X, X1, X2.
Код
Var x, x1, x2: array[1 .. n] Of integer;
Procedure bin_s;
Begin ... End;
{ Вот тут тебе надо найти номер элемента из массива X1 }
...
{ тут - элемента из массива X2 }
...
{ а вот тут - номер элемента из массива X }
Твои действия?
Или еще более коварный вариант - если все 3 массива имеют разную размерность...
Автор: klem4 26.02.2005 18:29
Вот :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 26.02.2005 19:38
Цитата(volvo @ 25.02.05 9:41)
Или еще более коварный вариант - если все 3 массива имеют разную размерность...
Я так понимаю, этот вариант не рассматривался?
Автор: klem4 26.02.2005 20:00
Щас сделаем ...
Автор: klem4 26.02.2005 23:19
Не могу найти ошибку
Код
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 26.02.2005 23:31
А в чем, собственно, ошибка? Эта программа отрабатывает.
Автор: klem4 26.02.2005 23:50
например 1,2,3,0,5 если искать 0 то возвращает nfind=0.
Или тока у меня ??))
Автор: volvo 26.02.2005 23:52
А как же упорядоченность? "Бинарный (двоичный) поиск, только для отсортированного массива"... Массив <1, 2, 3, 0, 5> не является отсортированным
Автор: klem4 27.02.2005 16:10
так точно!) ну значит теперь все в поряде
Автор: volvo 27.02.2005 19:15
Цитата(klem4 @ 27.02.05 11:10)
ну значит теперь все в поряде
Правда? А у меня еще несколько вопросов...
1. Описана функция... А что, собственно, она возвращает?
2. При работе с бОльшими массивами - проблемы... Попробуй, например, описать вот так:
Код
type
arrT=array[1..10000] of integer;
и запустить программу. Что произойдет? А ведь этот метод по определению желательно использовать для больших объемов данных... Так что еще не все..
Автор: volvo 28.02.2005 0:01
Проверь вот это:
Код
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.