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

Для: BattleMage
А что конкретно вызвало затруднение?
Если реализация бинарного поиска, то описание есть ]]>ЗДЕСЬ]]>. Про то как получить доступ к ячейкам StringGrid-а не мне рассказывать

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

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

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

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

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

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

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

Для: Kmet

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

 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 условием окончания цикла разобрался, теперь скажите: я то сделал или нет? :)

Попробуй:

while( k <= n )

И еще:

n=StringGrid2->RowCount - 1

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

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

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


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

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