Why does function that takes parameter as vector returns a garbage value?

Question

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

using namespace std;

bool compare(string a, string b) {
    return a < b;
}

int B_SEARCH(vector<string>::iterator ARR, int START, int END, string TARGET) {
    if (START > END)
        return 0;

    int MIDDLE = (START + END) / 2;

    cout << "CURRENT MIDDLE: " << MIDDLE << "\n";

    if (ARR[MIDDLE] == TARGET) {
        cout << "ARR[MIDDLE]: " << ARR[MIDDLE] << " "
             << "TARGET: " << TARGET << " And MIDDLE is: " << MIDDLE << "\n";
        return MIDDLE;
    } else if (ARR[MIDDLE] < TARGET)
        B_SEARCH(ARR, MIDDLE + 1, END, TARGET);
    else
        B_SEARCH(ARR, START, MIDDLE - 1, TARGET);
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int N, M, cnt = 0;

    cin >> N >> M;

    vector<string> ARR;
    vector<string> ANSWER;
    ARR.reserve(N);

    string temp;

    for (int i = 0; i < N; i++) {
        cin >> temp;
        ARR.push_back(temp);
    }

    vector<string>::iterator BEGIN = ARR.begin();
    vector<string>::iterator END = ARR.end();

    sort(BEGIN, END, compare);

    for (int i = 0, gbg; i < M; i++) {
        cin >> temp;
        if (gbg = B_SEARCH(BEGIN, 0, ARR.size() - 1, temp)) {
            cout << "B_SEARCH: " << gbg << "\n";
            ANSWER.push_back(temp);
            cnt++;
        }
    }

    cout << cnt << '\n';

    if (cnt)
        for (int i = 0; i < ANSWER.size(); i++)
            cout << ANSWER[i] << '\n';
}

This is a code that takes 2 integer as input and store value to N and M and repeat N times to get inputs as string to store them in vector array,
repeat M times more to check whether each input string is matched to string vectors array.

If I give inputs as

3 4
ohhe
charlie
base
obama
base
ohhe
clinton

Then ohhe,charlie,base will stored in vector array,
and tries to find obama,base,ohhe,clinton string is in string vector.
( I know it's confusing but I can't find better example to explain my situation :( )

After I run the code, I've realized that function B_SEARCH returns a memory address(maybe garbage value) instead of given MIDDLE variable's value.

To show some of by output, it would be like...

CURRENT MIDDLE: 1
CURRENT MIDDLE: 0
ARR[MIDDLE]: base TARGET: base AND MIDDLE is: 0
B_SEARCH: 6422116

I've wrote some letters for debug, and third line of output says MIDDLE which is return value is 0 but if I check the return value in main function, it says 6422116

How this happen...? I've never seen error like this.
Is it because of I've gave function's parameter as vector?

The only meaningful warning I see is "control reaches end of non-void function". But I'm sure `B_SEARCH` always reaches to its end — jadon, Mar 02 '21 at 04:08
But that doesn't seem to be the case. The only branch you're returning from is the first `if`. You should be *returning* the result of the recursive calls to `B_SEARCH`. — cigien, Mar 02 '21 at 04:15
I do have second return branch for `if(ARR[MIDDLE] == TARGET)` where returns `MIDDLE`. First branch is just for explicitly show the exit status. — jadon, Mar 02 '21 at 04:17
OHHH I get it now. I have to add `return` to those two recursive call right? — jadon, Mar 02 '21 at 04:21
Have a look at [Significance of ios_base::sync_with_stdio(false); cin.tie(NULL);](https://stackoverflow.com/q/31162367/3422102) and make sure you really want to do that. — David C. Rankin, Mar 02 '21 at 05:34

score 0 · Answer 1 · answered Mar 02 '21 at 04:31

Fix it by returning the value in your binary search recursive function, type is int but you use it like a void function:

return B_SEARCH(ARR, MIDDLE + 1, END, TARGET);
    else
      return  B_SEARCH(ARR, START, MIDDLE - 1, TARGET);
}

In recursive function you must always return value else there is no purpose for the operation!

PS: Also a while iterative would become an if in a recursive function

Why does function that takes parameter as vector returns a garbage value?

1 Answers1