Форум программистов, компьютерный форум CyberForum.ru

Бинарный поиск - C++

Восстановить пароль Регистрация
 
ABKA
7 / 7 / 0
Регистрация: 06.11.2013
Сообщений: 50
06.11.2013, 21:44     Бинарный поиск #1
Писал алгоритм бинарного поиска по массиву строк. В результате, почему-то, периодически функция не находит строку, которая есть.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binary_search(std::string** strlist, std::string key, int num)  
{
   int L = 0;            
  int R = num-1;    
 
  while (L <= R) {
    int m = (L + R)/2;
    if (strlist[1][m].compare(key)==0) return m;
    if (strlist[1][m].compare (key)>0) R = m-1;
    if (strlist[1][m].compare (key)<0) L = m+1;
  }
  return -1;
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2013, 21:44     Бинарный поиск
Посмотрите здесь:

Бинарный поиск C++
C++ Бинарный поиск
Бинарный поиск C++
Бинарный поиск C++
Бинарный поиск C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
chedman
80 / 79 / 2
Регистрация: 30.10.2013
Сообщений: 249
07.11.2013, 09:57     Бинарный поиск #2
Я так понимаю, что массив строк двумерный или это не так.
newbie666
Заблокирован
07.11.2013, 10:02     Бинарный поиск #3
Что за вело инжениринг ))) Используй std::binary_search
Ilot
07.11.2013, 10:20
  #4

Не по теме:

Цитата Сообщение от newbie666 Посмотреть сообщение
Что за вело инжениринг ))) Используй std::binary_search
Это называется "очумелые ручки" или как это там. ТС хочет реализовать бинарный поиск самомтоятельно как говорил почтальон Печкин "в целях повышения образованности". В чем вопрос?

ABKA
7 / 7 / 0
Регистрация: 06.11.2013
Сообщений: 50
07.11.2013, 12:38  [ТС]     Бинарный поиск #5
chedman, Массив можно вопринимать как одномерный, ибо поиск поводится только по arr[1][i].

newbie666, хотелось бы написать самому.

Проблема в том, что моя функция периодически выдает неправильный результат(
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
07.11.2013, 12:45     Бинарный поиск #6
Ну так может вы покажите какие результаты выдает ваш код и где вы видите ошибку. Согласитесь так будет легче вам помочь, если вы в этом заинтерессованы.
ABKA
7 / 7 / 0
Регистрация: 06.11.2013
Сообщений: 50
07.11.2013, 12:51  [ТС]     Бинарный поиск #7
Я вечером смогу показать весь код, но результаты следующие: когда на вход поступает массив из 4 строк(представим, что он одномерный), функция правильно находит положение всех строк, кроме третей. При поиске третей строки она возвращает -1 (строка не найдена)

Добавлено через 2 минуты
При этом при использовании обычного, тупого алгоритма поиска все верно
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
07.11.2013, 13:02     Бинарный поиск #8
Знаете я бы в вашем случае переписал алгоритм в виде рекурсии, а аргументы заменил бы на итераторы или указатели (это по желанию). Так как ваши условия не совсем очевидны. Например:
C++
1
while (L <= R)
Т.е. поиск прекратится если левая граница будет больше правой? Не думаю, что это хорошая идея...
chedman
80 / 79 / 2
Регистрация: 30.10.2013
Сообщений: 249
07.11.2013, 13:09     Бинарный поиск #9
Я так полагаю, что строки должны быть отсортированы. Это условие выполняется?
ABKA
7 / 7 / 0
Регистрация: 06.11.2013
Сообщений: 50
07.11.2013, 13:10  [ТС]     Бинарный поиск #10
А как этот алгоритм сделать в виде рекурсии?

Добавлено через 28 секунд
chedman, Да, конечно
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
07.11.2013, 13:31     Бинарный поиск #11
Таки переделал. Изучайте:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
int binary_search(string* strlist, string key, int num)
{
  int L = 0;
  int R = num;
  int m = L;
  do
  {
    if (strlist[m].compare(key)==0) return m;
    if (strlist[m].compare (key)>0) R = m;
    if (strlist[m].compare (key)<0) L = m;
    m = (L + R)/2;
  } while ((R - L) != 1);
  return -1;
 
}
int main(int argc, char* argv[])
{
    string arr[] = {"aa", "bb", "cc", "dd", "ee"};
    cout << binary_search(arr, "aa", 5) << endl;
    cout << binary_search(arr, "bb", 5) << endl;
    cout << binary_search(arr, "cc", 5) << endl;
    cout << binary_search(arr, "dd", 5) << endl;
    cout << binary_search(arr, "ee", 5) << endl;
    cout << binary_search(arr, "ff", 5) << endl;
    return 0;
}
А как этот алгоритм сделать в виде рекурсии?
Впринципе также только вместо изменения диапазона вызывать ф-ю. Однако знаете мне кажется с рекуррсией я погорячился. В данном случае проще без нее, а вот перейти к итераторам былобы самое то.

Добавлено через 10 минут
Вот тут у меня косяк:
C++
1
R = m;
Но почему-то программа работает
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 18:18     Бинарный поиск
Еще ссылки по теме:

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

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ABKA
7 / 7 / 0
Регистрация: 06.11.2013
Сообщений: 50
07.11.2013, 18:18  [ТС]     Бинарный поиск #12
Спасибо!)
Yandex
Объявления
07.11.2013, 18:18     Бинарный поиск
Ответ Создать тему
Опции темы

Текущее время: 08:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru