1

I am now learning C++, and started with tasks in LeetCode. The task is binarySearch. Got an issue with return statement when target found. Here is my solution:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int mid = nums.size() / 2;
        while (mid < nums.size() && mid >= 0) {
            cout << mid << ' ' << nums[mid] << endl; //for debuging
            if (nums[mid] == target) {
                cout << "WTF";    //PRINTS
                return mid;       // Doesn't work!
            }
            else if (target > nums[mid]) {
                mid += mid / 2;
            } 
            else if (target < nums[mid]) {
                mid -= mid / 2;
            } 
        }
        return -1;
    }
};

The problem is with return mid;. The output on test case [-1,0,3,5,9,12], target=9 is

Time Limit Exceeded
2 5
3 9
WTF3 5
2 3
1 0
1 0
1 0
1 0...

So, if statement works, but function continues working after return command. I've tried to compile same code with g++ and everything works nice.

Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
Garik Mkrtchyan
  • 23
  • 4
  • 2
    Start using a debugger. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). Also, **C++ must be learnt using a [good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) instead of by solving random online puzzles.** – Jason Mar 28 '23 at 08:41
  • 1
    Are you sure the function isn't called several times from `main()`? These kind of sites often run multiple tests of your code. – Yksisarvinen Mar 28 '23 at 08:41
  • What you get is not a compiler error. A compiler error is when the compiler detects something like a syntax or semantic error in the source code. Like trying to do `void return foo;` in your code. What you have is a *logical* error, that results in unwanted behavior. As mentioned, the way to solve that is to debug a [mre] locally on your own system. – Some programmer dude Mar 28 '23 at 08:44
  • I apologize. An compiler issue. I think the issue is with the compiler, because when compiling same code with another one, I get it working, – Garik Mkrtchyan Mar 28 '23 at 08:46
  • The output you are quoting doesn't match the test case at all. – john Mar 28 '23 at 08:46
  • The compiler is generating the correct code. Have you considered what @Yksisarvinen mentioned? What happens if you, in your own test program, call the function multiple times? And as also mentioned, ***use a debugger***. – Some programmer dude Mar 28 '23 at 08:47
  • 2
    Don't learn C++ from leetcode, you will only pickup bad habits. If you don't have access to books use : https://www.learncpp.com/ (it's pretty decent). Then check the https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines to see what you have missed. – Pepijn Kramer Mar 28 '23 at 08:48
  • 1
    @GarikMkrtchyan Compilers have hundreds of man/years development and millions of users world wide. Thinking that your 10 line program has found a compiler bug is not credible. – john Mar 28 '23 at 08:48
  • When tried to return outside of if statement, everything works nice. The problem is that code continues execution after the return statement – Garik Mkrtchyan Mar 28 '23 at 08:49
  • @GarikMkrtchyan It's actually perfectly common for compilers when given bugged code to produce different results. Including cases where one compiler produces working code and the other compiler does not. Not that I'm saying your code is bugged, just pointing out that this is how C++ is. – john Mar 28 '23 at 08:50
  • 1
    @GarikMkrtchyan I promise you that is not happening. Most likely as already mentioned LeetCode is supplying multiple test cases to your code. Alternatively for some reason LeetCode is not executing the code you think it is. – john Mar 28 '23 at 08:52
  • @Some programmer dude, tried what you mentioned, in my test program everything works just fine – Garik Mkrtchyan Mar 28 '23 at 08:55
  • @GarikMkrtchyan Also LeetCode uses g++ as it's compiler. Granted it might not be the same version of g++ as yours, but just more indication that the issue here is something other than the compiler. – john Mar 28 '23 at 08:55
  • Found an issue with multiple runs. Added ` static int counter = 0; cout << "Counter = " << counter << endl; ++counter; ` At the start of function. The output is - ` Counter = 0 3 5 4 9 WTFCounter = 1 3 5 2 3 1 0 1 0... ` So, the function is run after return another time. – Garik Mkrtchyan Mar 28 '23 at 09:05
  • 1
    pssst.... [`std::binary_search`](https://en.cppreference.com/w/cpp/algorithm/binary_search) , possible to implement in 2 lines by use of [`std::lower_bound`](https://en.cppreference.com/w/cpp/algorithm/lower_bound) – 463035818_is_not_an_ai Mar 28 '23 at 09:12
  • It's broken - try to search for 1 in `{2}` or `{1,2}` and you're stuck forever. (There are good reasons for the conventional implementation's keeping track of the range and not the midpoint.) – molbdnilo Mar 28 '23 at 09:16

1 Answers1

2

Your function implementation is wrong. For example when the vector nums contains only one element then the variable mid will not be changed

else if (target > nums[mid]) {
    mid += mid / 2;
} 
else if (target < nums[mid]) {
    mid -= mid / 2;
}

because the expression mid / 2 is equal to 0. As a result you will have an infinite loop.

The function can be implemented the following way

class Solution {
public:
    std::vector<int>::size_type search( const std::vector<int> &nums, int target ) 
    {
        std::vector<int>::size_type low = 0, high = nums.size();

        while ( low != high ) 
        {
            auto mid = low + ( high - low ) / 2;

            if ( target < nums[mid] ) 
            {
                high = mid;
            }
            else if ( nums[mid] < target ) 
            {
                low = mid + 1;
            } 
            else
            { 
                return mid;
            } 
        }

        return -1;
    }
};
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335