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

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

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

Бинарный поиск последнего нужного нам элемента - C++

20.03.2013, 12:25. Просмотров 429. Ответов 0
Метки нет (Все метки)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
  while (first < last)
               {
                    mid = (first + last) >> 1;
                    if (a[mid] >= x)
                    {
                         last = mid;
                    }
                    else
                    {
                         first = mid + 1;
                    }
 
               }
У меня есть упорядоченная последовательность чисел с возможными повторами чисел.
Самый быстрый метод посчитать количество повторов, найти первый и последний элемент и отнять их.
То есть , имея
C++
1
0 1 1 1 2 4 5
Находим первую 1 и последнюю 1 , отнимаем и вот он результат.
Вот только с написанием поиска который ищет последний элемент возникли проблемы.
иногда работает, иногда нет
C++
1
2
3
4
5
6
7
8
9
10
11
 while (first1 < last1)
               {
                    mid1 = (first1 + last1) >> 1;
                    if (a[mid1] <= x)
                    {
                         first1 = mid1;
                    }
                    else
                    {
                         last1 = mid1-1;
                    }
Может вы заметите ошибку?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2013, 12:25     Бинарный поиск последнего нужного нам элемента
Посмотрите здесь:

Найти номер последнего максимального элемента среди элементов, лежащих в диапазоне [c,d] и расположенных до первого четного элемента. C++
C++ Односвязный список. Вывести сумму последнего элемента и первого, предпоследнего и последнего и т.д.
C++ Бинарный поиск
C++ Списки языка C++ Удаление нужного элемента
C++ Бинарный поиск
C++ Бинарный поиск элемента массива
Многомерный массив. Дублирование значения первого элемента строки в значении последнего элемента предыдущей C++
Бинарный поиск элемента в массиве C++
C++ Цикл поиска позиции нужного элемента
Поиск индекса нужного элемента C++
C++ Цикл поиска позиции нужного элемента
C++ Двоичный (бинарный) поиск элемента в двумерном массиве

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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