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

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

Восстановить пароль Регистрация
 
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
03.03.2013, 14:20     Двоичный поиск в map #1
Здравствуйте. Помогите разобраться в следующей проблеме.
В общем, мне нужно реализовать двоичный поиск в 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 – тут же не численные значения, а строки...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.03.2013, 14:20     Двоичный поиск в map
Посмотрите здесь:

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

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

Приближенный двоичный поиск C++
двоичный поиск C++
Двоичный поиск C++

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

Или воспользуйтесь поиском по форуму:
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
03.03.2013, 19:51     Двоичный поиск в map #7
Цитата Сообщение от Delmellor Посмотреть сообщение
Понимаете, у меня задача состоит в том, чтобы использовать именно двоичный поиск
Если задача в том, чтобы двоичный поиск использовать, то map и find подходят как нельзя более кстати. Если же требуется его реализовать самостоятельно, то следуй дельному совету kamre.
Yandex
Объявления
03.03.2013, 19:51     Двоичный поиск в map
Ответ Создать тему
Опции темы

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