§ 19. Бинарный поиск в отсортированном массиве
Упражнения
1. Задан упорядоченный массив (вектор) из целых чисел. Прочитать данные из файла. Можно воспользоваться файлом, который был получен при решении задач на сортировку массива. Воспользоваться алгоритмом бинарного поиска и выполнить указанные действия.
- Получить количество элементов равных x. Массив упорядочен в порядке неубывания.
- Удалить элемент, равный x. (Предполагается, что такой элемент существует и является единственным.) Массив упорядочен в порядке неубывания.
- Вставить элемент, равный x, не нарушая упорядоченности. (Такой элемент может быть.) Массив упорядочен в порядке невозрастания.
- Удалить из исходного массива все элементы, которые равны элементам другого упорядоченного массива. Массив упорядочен в порядке невозрастания.
2. Задан вектор строк, элементами которого являются фамилии. Данные прочитать из файла. Фамилии отсортированы в алфавитном порядке. Написать программы для решения задач, используя метод бинарного поиска.
- Определить, сколько человек в списке после Иванова. (Предполагается, что если такая фамилия есть, то она — единственная в списке.)
- Определить, сколько в списке людей с фамилией Иванов. (Предполагается, что такая фамилия есть в списке.)
- В список нужно вставить фамилию, введенную с клавиатуры. Определить место, на которое должна быть вставлена эта фамилия.
3. Оформить запрос на поиск в списке фамилий, начинающихся на какую-либо букву. В качестве ответа получить все найденные фамилии и их номера.