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

Тема в разделе "Borland C++ Builder & Kylix", создана пользователем BattleMage, 19 сен 2007.

  1. BattleMage

    BattleMage Гость

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

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    Для: BattleMage
    А что конкретно вызвало затруднение?
    Если реализация бинарного поиска, то описание есть ЗДЕСЬ. Про то как получить доступ к ячейкам StringGrid-а не мне рассказывать :)
     
  3. Kmet

    Kmet Well-Known Member

    Регистрация:
    25 май 2006
    Сообщения:
    1.017
    Симпатии:
    1
    std::binary_search
    откуда такая любовь к велосипедам? =)
     
  4. BattleMage

    BattleMage Гость

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

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

    Kmet Well-Known Member

    Регистрация:
    25 май 2006
    Сообщения:
    1.017
    Симпатии:
    1
    стандарная, стандартная,а раз стандартная, то rtfm
     
  6. BattleMage

    BattleMage Гость

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

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

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    <!--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]
     
  8. BattleMage

    BattleMage Гость

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

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

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    <!--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]
    Попробуй:
    Код (Text):
    while( k <= n )
    И еще:
    Код (Text):
    n=StringGrid2->RowCount - 1
     
  10. BattleMage

    BattleMage Гость

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

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

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    <!--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]
    В этом случае теряется скорость, присущая бинарному поиску
     
  12. BattleMage

    BattleMage Гость

    Большое, пребольшое спасибо!!!
     
Загрузка...

Поделиться этой страницей