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

[BattleMage]

Ещё раз доброго времени суток
У меня очередной вопрос. Воту меня есть таблица StringGrid1. В ней два столбца. Элементы первого столбца упорядочены по алфавиту. Как мне выполнить по первому стобцу поиск элемента? Поиск не обычный перебором до первого совпадения, а бинарный.
если не трудно: небольшой кусочек кода, буду разбираться...

 

[European]

Для: BattleMage
А что конкретно вызвало затруднение?
Если реализация бинарного поиска, то описание есть

Ссылка скрыта от гостей

. Про то как получить доступ к ячейкам StringGrid-а не мне рассказывать

 

[Kmet]

std::binary_search
откуда такая любовь к велосипедам? =)

 

[BattleMage]

European: ищем не в числовом массиве: M = (Lb + Ub)/2; (этой из той ссылки, что ты дал)
как такое выполнить со словами?

Kmet: std::binary_search это что такое? какая то стандартная функция бинарного поиска? если да, то как ей пользоваться и как выглядит её прототип?

 

[Kmet]

стандарная, стандартная,а раз стандартная, то rtfm

 

[BattleMage]

Kmet: дай ссылочку нормальную, чтобы было ясно как пользоваться. весь инет забит каким-то мусором

А вообще хотелось бы сделать без стандартной функции, понимаю что глупо, но боюсь препод не оценит мою смекалку

 

[European]

<!--QuoteBegin-BattleMage+19:09:2007, 09:58 -->
<span class="vbquote">(BattleMage @ 19:09:2007, 09:58 )</span><!--QuoteEBegin-->ищем не в числовом массиве: M = (Lb + Ub)/2

[snapback]78762" rel="nofollow" target="_blank[/snapback]​

[/quote]
Тебе нужны не значения строк, а их индексы. Т.е. Lb = 0; Ub = кол-во строк. Далее вместо операций сравнения чисел в примере используешь strcmp. Хотя так как ты пишешь в Билдере, то строки имеют тип AnsiString, для которого реализованы функции для сравнения

Для: Kmet
<!--QuoteBegin-Kmet+19:09:2007, 09:36 -->
<span class="vbquote">(Kmet @ 19:09:2007, 09:36 )</span><!--QuoteEBegin-->откуда такая любовь к велосипедам? =)

[snapback]78752" rel="nofollow" target="_blank[/snapback]​

[/quote]

<!--QuoteBegin-BattleMage+19:09:2007, 10:27 -->
<span class="vbquote">(BattleMage @ 19:09:2007, 10:27 )</span><!--QuoteEBegin-->А вообще хотелось бы сделать без стандартной функции, понимаю что глупо, но боюсь препод не оценит мою смекалку

[snapback]78773" rel="nofollow" target="_blank[/snapback]​

[/quote]

 

[BattleMage]

Вот что-то написал:
Это действительно бинарный поиск или бред какой-то, который правильно ищет?

 int k=0, n=StringGrid2->RowCount,m;
flag=0;
while(1)
{
m=(n+k)/2;
if (strcmp(Edit1->Text.c_str(),StringGrid2->Cells[0][m].c_str())==NULL)
{
flag=1;
break;
}
if (strcmp(Edit1->Text.c_str(),StringGrid2->Cells[0][m].c_str())<0) n=m-1;
if (strcmp(Edit1->Text.c_str(),StringGrid2->Cells[0][m].c_str())>0) k=m+1;
}
if (flag==1) ShowMessage("Идентификатор <"+Edit1->Text+
"> имеет тип <"+StringGrid2->Cells[1][m]+">");
else ShowMessage("Идентификатор не найден!");

И вот ещё: если вводишь такой элемент, которого нет в таблице, то прога зависает. Может какое-то другое условие завершения цикла написать?



C условием окончания цикла разобрался, теперь скажите: я то сделал или нет?

 

[European]

<!--QuoteBegin-BattleMage+19:09:2007, 12:26 -->
<span class="vbquote">(BattleMage @ 19:09:2007, 12:26 )</span><!--QuoteEBegin-->Может какое-то другое условие завершения цикла написать?

[snapback]78795" rel="nofollow" target="_blank[/snapback]​

[/quote]
Попробуй:

while( k <= n )

И еще:

n=StringGrid2->RowCount - 1

 

[BattleMage]

European, спасибо. Твой способ работает. Я тоже придумал один: ещё одну переменную завожу и в каждой итерации инкремирую её, если не было совпадения слов. а условие такое: while (b<StringGrid2->RowCount/2);
Вобщем это не важно, главное работает

а почему n=StringGrid2->RowCount - 1, а не n=StringGrid2->RowCount?

 

[European]

<!--QuoteBegin-BattleMage+19:09:2007, 13:00 -->
<span class="vbquote">(BattleMage @ 19:09:2007, 13:00 )</span><!--QuoteEBegin-->а почему n=StringGrid2->RowCount - 1, а не n=StringGrid2->RowCount?

[snapback]78803" rel="nofollow" target="_blank[/snapback]​

[/quote]
Индексация с нуля начинается, а RowCount содержит количество строк

<!--QuoteBegin-BattleMage+19:09:2007, 13:00 -->
<span class="vbquote">(BattleMage @ 19:09:2007, 13:00 )</span><!--QuoteEBegin-->Я тоже придумал один: ещё одну переменную завожу и в каждой итерации инкремирую её, если не было совпадения слов. а условие такое: while (b<StringGrid2->RowCount/2);
Вобщем это не важно, главное работает

[snapback]78803" rel="nofollow" target="_blank[/snapback]​

[/quote]
В этом случае теряется скорость, присущая бинарному поиску

 

[BattleMage]

Большое, пребольшое спасибо!!!