Блог пользователя abh123

algorithm behind upperbound in c++
Автор abh123, 11 лет назад, По-английски

i am using upperbound and lowerbound in c++ regularly but i don't know actual algorithm behind this??? Plzz help..

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

It's a simple binary search.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://www.cplusplus.com/reference/algorithm/upper_bound/

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually i m not able to understand this step. std::advance (it,step);

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      bcoz this step is linear and this will increase it's complexity..?

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        its just equal to it+step in our case, works for O(1)

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It's O ( 1 ) when you have random access iterators, on non random access iterators it has linear complexity.

          → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

http://www.cplusplus.com/reference/algorithm/lower_bound/

→ Ответить