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

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

Войти
Регистрация
Восстановить пароль
 
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
#1

Двоичный поиск в map - C++

03.03.2013, 14:20. Просмотров 1013. Ответов 6
Метки нет (Все метки)

Здравствуйте. Помогите разобраться в следующей проблеме.
В общем, мне нужно реализовать двоичный поиск в map по ключам. Понятное дело, тот факт, что ключи в map отсортированы, нас только радует.
Ключи у меня - string. ; т.е. их сортировка идёт по алфавиту. Значения тоже string. У меня значение, которое нужно найти в mymap двоичным поиском по ключам.

Основные вопросы:
1) Как получить доступ к нужному элементу map? Мне нужно что-то типа итератора, который на него указывает.
2) mymap.begin() возвращает итератор, правильно?

Проблема в том, что не могу "срезать". Всё начинается с того, что есть итератор, указывающий на mymap.begin(), и есть итератор, указывающий на mymap.end()
Начинаю писать двоичный поиск:
while (iter1->first < iter2->first) // пока отрезок не пуст
а вот тут нужен итератор, указывающий на... средний элемент в mymap.

Т.е. когда мы, например, работаем с одномерным int массивом a размера N, у которого всё отсортировано, там всё просто... L=0, R=N-1 – индексы левый и правый соответственно; X - то, что в нём найти нужно, и пишем
C++
1
2
3
4
5
6
7
while (L<=R) {
   int M = (L+R)/2 ;  // индекс середки
   if (a[M] == X) return M; 
   if (a[M]>X) R=M-1; 
   else L=M+1; 
   // и т.п. всё легко
   }
А как быть в моей ситуации? Что в данном случае "индекс середки"? Как обратиться к элементу, лежащему между? Короче, суть в том, что непонятно, как обратиться "по индексу" к элементу map (который <string, string>). Я ж не могу написать (iter1->first + iter2->first)/2 – тут же не численные значения, а строки...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.03.2013, 14:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Двоичный поиск в map (C++):

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

Двоичный поиск - C++
Помогите пожалуйста с двоичным поиском: нужно найти абитуриента с 287 баллами методом двоичного поиска.. #include &lt;iostream.h&gt; ...

двоичный поиск - C++
Подскажите, пожалуйста, в вопросе: Какое дополнительное требование к массиву может быть применено при двоичном поиске, что бы определить...

Двоичный поиск - C++
Нашел на форуме двоичный поиск, не подскажите как нужно изменить код, что бы программа выводила еще и индекс, в котором находится введенное...

Двоичный поиск - C++
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды. #include &lt;stdafx.h&gt; #define N 10 ...

Двоичный поиск - C++
Добрый день. Помогите найти ошибку в двоичном поиске. Вот код: #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int...

6
DU
1484 / 1130 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
03.03.2013, 14:45 #2
какая-то странная задача. в мапине уже есть функция find, которая и пользуется тем, что в мапине все отсортировано. она возвращает нужный итератор, если найдет что-то. или она вас чем-то не устраивает?
0
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
03.03.2013, 14:56 #3
Цитата Сообщение от Delmellor Посмотреть сообщение
мне нужно реализовать двоичный поиск в map по ключам
А зачем, если уже есть std::map::find? К деталям реализации map доступа нет, так что итераторами можно только последовательно получать элементы.
0
Nick Alte
Эксперт С++
1639 / 1011 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
03.03.2013, 14:57 #4
Элементы в map расположены в дереве, так что несмотря на упорядоченность, о произвольном доступе можно забыть. Для поиска следует применять метод find - в конце концов, map именно для того и придумывали, чтобы самому поиски не писать.
0
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
03.03.2013, 17:23  [ТС] #5
Ммм... спасибо за ответы; не знал про find.
Но тема не исчерпана. Ведь для find'a нужен конкретный ключ, который совпадает с ключом map элемента, на который возвращается итератор. А у меня его (ключа) нет... мне нужен элемент строго между итераторами; ведь в этом суть двоичного поиска! – постоянно сокращать отрезок.
Просто тогда расширю вопрос... Как реализовать двоичный поиск вообще в такой ситуации?

Обновлено: прочитал посты выше внимательнее... Понимаете, у меня задача состоит в том, чтобы использовать именно двоичный поиск; map использовать или не map – неважно; важна реализация двоичного поиска. А я выбрал для этого map, потому что задача про отсортированную по алфавиту телефонную книгу, в которой нужно использовать двоичный поиск, чтобы найти абонентов по заданному номеру.
0
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
03.03.2013, 17:32 #6
Цитата Сообщение от Delmellor Посмотреть сообщение
важна реализация двоичного поиска
Тогда тебе нужно брать контейнер с RandomAccessIterator, а map для этого не подходит. Можно взять std::vector, предварительно самому отсортировав его через std::sort.
1
Nick Alte
Эксперт С++
1639 / 1011 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
03.03.2013, 19:51 #7
Цитата Сообщение от Delmellor Посмотреть сообщение
Понимаете, у меня задача состоит в том, чтобы использовать именно двоичный поиск
Если задача в том, чтобы двоичный поиск использовать, то map и find подходят как нельзя более кстати. Если же требуется его реализовать самостоятельно, то следуй дельному совету kamre.
1
03.03.2013, 19:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.03.2013, 19:51
Привет! Вот еще темы с ответами:

Приближенный двоичный поиск - C++
Доброго времени суток, форумчане. Задача такая: В первой строке входных данных содержатся числа N и K (0 &gt; N,K &gt;100001 ). Во второй...

Двоичный (бинарный) поиск - C++
Вот такой вот вопрос: Есть например такой линейный массив 1 1 1 1 2 3 4 5 6 Вводят какое-то число и нужно проверить сколько...

Двоичный(бинарный) поиск - C++
Столкнулся с такой проблемой. использую бинарный поиск в упорядоченном массиве чисел для поиска количества повторений нужного мне числа К...

Нерекурсивный двоичный поиск - C++
необходимо написать на С++ двоичный поиск в рекурсивном варианте. вот пример рекурсивной ф-ции двоичного поиска: int BinSerch(int...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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