Divide function returns wrong value

Question

I have a function which will supposedly check if there's an indices i such that it is equal to v[i]. V is a strictly ascending ordered vector. It needs to be done in O(logn) and I thought about divide. I was never really familiar with recursion. I wrote this code and I don't really know why it won't work. Something's missing. If I put cout << mid instead of return it will show the right value, but I guess that's not the proper way to do it, frankly. In this stage the mid value returned is 7, and I don't know why.

Here's the code.

int customDivide(vector <int>& v, int left, int right)
{
    if(left <= right)
    {
        int mid = (left+right)/2;
        if(mid == v[mid]){
            //cout<<mid<<" ";
            return mid;
        }
    customDivide(v,left,mid-1);
    customDivide(v,mid+1,right);
    }
}

Answer 1

As a result of all the help involved here, I finally understood what the problem was.

• 1st of all - It didn't take advantage of the fact that the vector was strictly sorted.
• 2nd - Every function in the stack returns something now.

int customDivide(vector <int>& v, int left, int right)
{
    if(left <= right)
    {
        int mid = (left+right)/2;
        if(mid == v[mid])
            return mid;
        else if(v[mid] < mid)
            return customDivide(v,mid+1,right);
        else
            return customDivide(v,left, mid-1);
    }
    return -1;
}

Thanks a lot for all your help!

Answer 2

Two problems exist here, and I will attempt to explain them with an analogy of finding a lost dog in your neighborhood.

1. You are not returning a value from the function, unless you found the correct element immediately. You promise to return a value (an int) but you don't always do it.

   This is like promising to send the dog owner a letter to indicate where their lost dog can be found. You check your garden and if you find the dog, you send a letter - that works. If you didn't find the dog, you go to your neighbors and have them promise to send you a letter if they find the dog, using the same method as you did (recursion). The problem is that in this case you are not reading or forwarding their letters (the return values from your two recursive function calls at the end) - you are just throwing these letters away. Worse, you are not actually sending back the letter to the guy looking for his dog if you didn't find it yourself (no return after the calls). Your code seems to assume that the neighbors will automatically send the letter to the dog owner - that is not how return works, it just sends the letter to the previous person in the chain (in code terms, the call stack), so if that person throws it into the trash right away, the system won't work.

2. You cannot get O(log(n)) performance if you unconditionally recurse to both sides.

   If you always ask all your neighbors (and they ask all of theirs), you will have literally every person in the neighborhood looking for the dog. That's O(n). You must identify which of your two neighbors should look for the dog (e.g. by looking at the trail the dog left) and only ask that one. This way you halve the number of people that might have to search for the dog at each step, giving you O(log(n)) performance.

   This "trail" is something you need to know beforehand. In your case, it is not clear what that could be - the dog could be anywhere (all elements could have random values) and you have no idea where to go looking. You need to figure out this detail of the task to get to your O(log(n)) time. It could be that vector elements are strictly increasing (see @Jarod42's comment), i.e. there are no duplicate elements and each one is larger than the previous one. In that case you can decide that only one of the two remaining halves can possibly contain what you are looking for, thus recursing there.

(Yes I know, the analogy breaks down unless your neighborhood is shaped like a binary tree with you at the top and a non-reciprocal definition of "neighbors".)