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

Бинарный поиск (самое левое вхождение) - C++

Восстановить пароль Регистрация
 
Help
0 / 0 / 0
Регистрация: 27.06.2014
Сообщений: 5
23.07.2014, 12:21     Бинарный поиск (самое левое вхождение) #1
C++
1
2
3
4
5
6
7
int binsearch (int a[],int key, int l, int h)
{
    int medium;
    medium=(l+h)/2;
    if (l>h) return (l);
    if (a[medium]>key) return (binsearch (a,key,l,medium-1)); else return (binsearch (a,key,medium+1,h));
}
Данный алгоритм находит самое правое вхождение элемента. Как найти самое левое?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2014, 12:21     Бинарный поиск (самое левое вхождение)
Посмотрите здесь:

C++ Бинарный поиск
Бинарный поиск C++
Бинарный поиск C++
C++ Бинарный поиск
Бинарный поиск C++
Бинарный поиск C++
Бинарный поиск C++
Поиск числа в двумерном массиве (бинарный поиск) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
24.07.2014, 05:43     Бинарный поиск (самое левое вхождение) #2
C++
1
2
3
4
5
6
7
8
9
10
11
    int a[15] = { 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 10 };
    int x;
    cin >> x;
    int l = 0, r = 15;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(a[mid] < x)
            l = mid;
        else r = mid;
    }
    cout << r << endl;
инвариант должен быть: http://www.cyberforum.ru/cgi-bin/latex.cgi?l указывает на меньшие, http://www.cyberforum.ru/cgi-bin/latex.cgi?r - на большие либо равные.
Yandex
Объявления
24.07.2014, 05:43     Бинарный поиск (самое левое вхождение)
Ответ Создать тему
Опции темы

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