0

I was to solve one question on hackerrank related to lower bound in C++. My code was able to pass all the test cases which had no time limit but failed in all time bound test cases. You can find the hackerrank question from this link:

https://www.hackerrank.com/challenges/cpp-lower-bound/problem?utm_campaign=social-buttons&utm_medium=linkedin&utm_source=challenge

Below is my code. Please tell me how I can optimize it.

#include <vector>
#include <iostream>
#include <algorithm>

int main() {
    std::vector<int> v;
    int elementCount = 0, queryCount = 0, tempElement = 0;
    std::cin >> elementCount;

    for(int i=0; i<elementCount; ++i)
    {
        std::cin >> tempElement;
        v.push_back(tempElement);
    }

    std::vector<int>::iterator elementPosition;
    const std::vector<int>::iterator midElement = v.begin() + v.size()/2;
    std::cin >> queryCount;

    for(int q=0; q<queryCount; ++q)
    {
        std::cin >> tempElement;
        if(tempElement <= *midElement)
        {
            elementPosition = find(v.begin(), midElement+1, tempElement);
            if(elementPosition == (midElement+1))
            {
                elementPosition = lower_bound(v.begin(), midElement, tempElement);
                std::cout << "No " << (elementPosition-v.begin())+1 << std::endl;
            }
            else
            {
                std::cout << "Yes " << (elementPosition-v.begin())+1 << std::endl;
            }
        }
        else
        {
            elementPosition = find(midElement+1, v.end(), tempElement);
            if(elementPosition != v.end())
            {
                std::cout << "Yes " << (elementPosition-v.begin())+1 << std::endl;
            }
            else
            {
                elementPosition = lower_bound(midElement+1, v.end(), tempElement);
                std::cout << "No " << (elementPosition-v.begin())+1 << std::endl;
            }
        }
    }
    return 0;
}
PINAKIN BRAHMIN
  • 13
  • 2
  • 1
    start with vector::reserve – Waqar Aug 02 '20 at 18:49
  • 2
    `find(v.begin(), midElement+1, tempElement)` This does a linear search through the vector. They probably expect you to do a binary search (`lower_bound`). – Justin Aug 02 '20 at 18:49
  • 3
    Use a profiler. – n. m. could be an AI Aug 02 '20 at 18:49
  • 5
    It sounds like it's time to run a profiler. Figuring out which statements take the longest is their main purpose. – chris Aug 02 '20 at 18:49
  • @Justin i thought of using binary_search but to solve the problem i need to print index of the element if found but binary_search only return bool value that's why i am using find to accomplish both the tasks. – PINAKIN BRAHMIN Aug 02 '20 at 18:58
  • @n.pronouns'm. I don't know about profiler. I will look into it. Thank you. – PINAKIN BRAHMIN Aug 02 '20 at 19:00
  • @Chris I don't know about profiler. I will look into it. Thank you – PINAKIN BRAHMIN Aug 02 '20 at 19:00
  • What do you hope to learn from these contest/challenge/competitive coding/hacking sites? If it's to learn C++, you won't learn anything there. Like in this case, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program either runs slow, or fails to handle an obscure edge case. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Aug 02 '20 at 19:00
  • @Sam Varshavchik i am using this platform to practice whatever i have learnt about C++. – PINAKIN BRAHMIN Aug 02 '20 at 19:04
  • Every C++ textbook has plenty of practice examples that are designed to improve your understanding of the material that's been presented in each chapter. You will find those examples far more useful and informative than this. Does this "hackerrank" web site teach you how to properly implement a binary search? Of course not. You will only find an explanation, and some examples, in a textbook. – Sam Varshavchik Aug 02 '20 at 19:07
  • @Sam Varshavchik You're right. So can you suggest me any good book so that i can gain more knowledge about best practices. – PINAKIN BRAHMIN Aug 02 '20 at 19:10
  • See stackoverflow's [canonical list of C++ textbooks](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Aug 02 '20 at 19:11
  • @Sam Varshavchik Thank you. I will checkout the list. – PINAKIN BRAHMIN Aug 03 '20 at 07:50

1 Answers1

0

You have over complicated the solution with unnecessary find() + lower_bound.

  • Just use lower_bound() to find the element
  • If found, print yes
  • If not, print no
    auto elementPosition = lower_bound(v.begin(), v.end(), tempElement);
    size_t pos = std::distance(v.begin(), elementPosition);
    if (v[pos] == tempElement) {
        //print yes
    } else {
       // print no
    }
Waqar
  • 8,558
  • 4
  • 35
  • 43