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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ABKA
7 / 7 / 0
Регистрация: 06.11.2013
Сообщений: 50
#1

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

06.11.2013, 21:44. Просмотров 1049. Ответов 11
Метки нет (Все метки)

Писал алгоритм бинарного поиска по массиву строк. В результате, почему-то, периодически функция не находит строку, которая есть.
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;
 
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2013, 21:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Бинарный поиск (C++):

Поиск числа в двумерном массиве (бинарный поиск) - C++
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и бинарным(двоичным). Первый работает на ура. Второй...

Бинарный поиск - C++
Здравствуйте, помогите пожалуйста написать бинарный поиск одного элемента, текст читается из файла. Лабу сдавать в понедельник а я не знаю...

Бинарный поиск - C++
Реализуйте алгоритм бинарного поиска. Входные данные В первой строке входных данных содержатся натуральные числа N и K . Во второй...

Бинарный поиск - C++
за какое время работает бинарный поиск?

Бинарный поиск - C++
Вообщем, написал бинарный поиск, а он не работает для ключа со значением 9, может кто объяснить, как решить эту проблему? А ещё я не совсем...

Бинарный поиск - C++
Найти индекс расположения числа 15 в массиве на 20 элементов и сумму элементов предшествующих ему. Методом бинарного поиска. Вот код в...

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

Не по теме:

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

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

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

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

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

Добавлено через 28 секунд
chedman, Да, конечно
0
Ilot
Модератор
Эксперт С++
1811 / 1168 / 229
Регистрация: 16.05.2013
Сообщений: 3,082
Записей в блоге: 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;
Но почему-то программа работает
1
ABKA
7 / 7 / 0
Регистрация: 06.11.2013
Сообщений: 50
07.11.2013, 18:18  [ТС] #12
Спасибо!)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 18:18
Привет! Вот еще темы с ответами:

Бинарный поиск - C++
Всем привет! У меня вот тут маленькая проблемка! Помогите исправить, а то сама что-то не могу!! (( Когда прога просит ввести ключ...

Бинарный поиск - C++
Каким образом выполнить бинарный поиск определнного значения в отсортированном массиве?

Бинарный поиск - C++
Прочитал статью на хабре, о том, что только 10 проц программистов смогут реализовать бин поиск. Раньше никогда с ним не имел дело, прочитав...

Бинарный поиск c++ - C++
1) последовательного поиска максимального элемента в одномерном динамическом массиве; 2) бинарного поиска количества нулевых элементов...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.11.2013, 18:18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru