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

Здравствуйте. Помогите разобраться в следующей проблеме.
В общем, мне нужно реализовать двоичный поиск в 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 - то, что в нём найти нужно, и пишем
А как быть в моей ситуации? Что в данном случае "индекс середки"? Как обратиться к элементу, лежащему между? Короче, суть в том, что непонятно, как обратиться "по индексу" к элементу map (который <string, string>). Я ж не могу написать (iter1->first + iter2->first)/2 – тут же не численные значения, а строки...

0

какая-то странная задача. в мапине уже есть функция find, которая и пользуется тем, что в мапине все отсортировано. она возвращает нужный итератор, если найдет что-то. или она вас чем-то не устраивает?

0

Сообщение от Delmellor мне нужно реализовать двоичный поиск в map по ключам

А зачем, если уже есть std::map::find? К деталям реализации map доступа нет, так что итераторами можно только последовательно получать элементы.

0

Элементы в map расположены в дереве, так что несмотря на упорядоченность, о произвольном доступе можно забыть. Для поиска следует применять метод find - в конце концов, map именно для того и придумывали, чтобы самому поиски не писать.

0

Ммм... спасибо за ответы; не знал про find.
Но тема не исчерпана. Ведь для find'a нужен конкретный ключ, который совпадает с ключом map элемента, на который возвращается итератор. А у меня его (ключа) нет... мне нужен элемент строго между итераторами; ведь в этом суть двоичного поиска! – постоянно сокращать отрезок.
Просто тогда расширю вопрос... Как реализовать двоичный поиск вообще в такой ситуации?

Обновлено: прочитал посты выше внимательнее... Понимаете, у меня задача состоит в том, чтобы использовать именно двоичный поиск; map использовать или не map – неважно; важна реализация двоичного поиска. А я выбрал для этого map, потому что задача про отсортированную по алфавиту телефонную книгу, в которой нужно использовать двоичный поиск, чтобы найти абонентов по заданному номеру.

0

Сообщение от Delmellor важна реализация двоичного поиска

Тогда тебе нужно брать контейнер с RandomAccessIterator, а map для этого не подходит. Можно взять std::vector, предварительно самому отсортировав его через std::sort.

1

Сообщение от Delmellor Понимаете, у меня задача состоит в том, чтобы использовать именно двоичный поиск

Если задача в том, чтобы двоичный поиск использовать, то map и find подходят как нельзя более кстати. Если же требуется его реализовать самостоятельно, то следуй дельному совету kamre.

1