бинарный поиск

[1n0y]

собстно решил проапгрейдить поиск в своём удоляторе до бинарного. всё бы нечего, но результаты простого перебора и бинарного поиска заметно отличаются - в объёмных базах бинарный не находит примерно 10% совпадений. wtf?!


вот кусок бинарного:

//f4, f5 - стринглисты

f5.sort;
f4.sort;
while I<=f4.Count-1 do
begin
verh:=0;
niz:=f5.count;
found:=FALSE;
repeat
sred:=trunc((niz-verh)/2)+verh;
if AnsiPos(f4.Strings[I],f5.strings[sred])<>0
then found:=TRUE
else
if f4.Strings[I < f5.strings[sred]
then niz:=sred-1
else verh:=sred+1;
until (verh > niz) or found or (verh = f5.count);
if found
then
begin
form1.Memo6.Lines.Add(f5.Strings[sred]);
I:=I+1;
end
else
I:=I+1;
end


естественно, все стринглисты сортирую перед поиском.
вчомпроблема? или это такая фича бинарного поиска? :)

[AlexTheC0d3r]

собстно решил проапгрейдить поиск в своём удоляторе до бинарного. всё бы нечего, но результаты простого перебора и бинарного поиска заметно отличаются - в объёмных базах бинарный не находит примерно 10% совпадений. wtf?!


вот кусок бинарного:

//f4, f5 - стринглисты

f5.sort;
f4.sort;
while I<=f4.Count-1 do
begin
verh:=0;
niz:=f5.count;
found:=FALSE;
repeat
sred:=trunc((niz-verh)/2)+verh;
if AnsiPos(f4.Strings[I],f5.strings[sred])<>0
then found:=TRUE
else
if f4.Strings[I < f5.strings[sred]
then niz:=sred-1
else verh:=sred+1;
until (verh > niz) or found or (verh = f5.count);
if found
then
begin
form1.Memo6.Lines.Add(f5.Strings[sred]);
I:=I+1;
end
else
I:=I+1;
end


естественно, все стринглисты сортирую перед поиском.
вчомпроблема? или это такая фича бинарного поиска? :)

мб все из-за AnsiPos?

[1n0y]

нублин, юзая простой перебор всё ведь чудесно работает с AnsiPos..

[AlexTheC0d3r]

попробуй pos();

[1n0y]

неа, не помогло..

[sn0w]

это все потуму что строки терминируются ключевым символом, в дос (не помню какая инт) это был $, строковые функции си - 0, а в паскале понятия не имею. для поиска двоичных данных функции поиска подстрок вообще невозможно использовать.

сложного ниче нет. берешь массив паттерна и массив данных, и едешь по массиву сравнивая первый символ паттерна с текущим указателем, если не совпадет - следующий, если совпал - сверяешь второй и тд