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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Получить матрицу с использованием указателей http://www.cyberforum.ru/cpp-beginners/thread799365.html
Здравствуйте! Дана действительная квадратная матрица порядка 2n. Получить новую матрицу, переставляя её блоки размера nxn. Программа есть, готова, только нужно сделать её с использованием указателей. Тут мне подсказали что вот это - *(*(a+i)+j) нужно куда то примостить, у меня вообще с указателями тяжко, можете подсказать чего? Ниже программа без указателей и как передвинуть блоки. #include...
C++ Сочетания оператора цикла и условного оператора вывести на экран все числа a от до b , кратные некоторому числу c http://www.cyberforum.ru/cpp-beginners/thread799363.html
Нахождение целого числа по информации о его цифрах C++
нахождение целого числа по информации о его цифрах! в трехзначном числе зачеркнули его последнюю цифру когда в оставшимся двузначном числе переставили цифры а затем приписали к ним слева последнюю цифру числа x, то получилось число n. По заданному n найти число x( значение n вводится с клавиатуры 1<=n<=999 и при это число единиц в n не равно нулю) Добавлено через 1 час 54 минуты С++
C++ Использование функции sort
Часто видел как в алгоритме std::sort(v.begin(),v.end(),Less); // импользуют самонаписанную функцию Less разве нет для этой функции аналога в STL своеобразный аналог min,max только возвращающие bool'ean значение ?
C++ Зависает при компиляции программы с классами http://www.cyberforum.ru/cpp-beginners/thread799353.html
При запуске на компиляцию, просто висняк получается.. Помню, на лекциях говорили, якобы после описания класса и методов надо точку с запятой ставить, но не помогает. Посмотрите, плиз!! #include<iostream> #include<math.h> using namespace std; class vector { private: int x1; int y1;
C++ Строки Дана строка. Преобразуйте ее так, чтобы сначала следовали цифровые символы, а затем все остальные. Порядок следования символов между собой не изменять. Как ее решить на Visual C++ 2008??? подробнее

Показать сообщение отдельно
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
03.03.2013, 14:20     Двоичный поиск в 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 - то, что в нём найти нужно, и пишем
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 – тут же не численные значения, а строки...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 17:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru