returning 32767 instead of -1 in Binary Search

[memepapa]

Need help reviewing the recursive code.

The iterative version works, but with the recursive version, it returns 32767 instead of -1 when "6" cannot be found.

additionally, "5" and "10" are in the array, but the code is not returning mid with their index positions...

#include <iostream>


int binarySearch(int * arr, int low, int high, int key) {
    if(low > high)
        return -1;

    int mid=(low+high)/2;

    if(arr[mid] == key)
        return mid;

    else if(arr[mid]<key) {
        binarySearch(arr, mid+1, high, key);
    }
    else{
        binarySearch(arr, low, mid-1, key);
    }
    
}

int main() {

    int arr[] = {1,3,5,7,8,9, 10, 11, 13};

    std::cout << binarySearch(arr, 0, 8, 5) << std::endl;

    std::cout << binarySearch(arr, 0, 8, 6) << std::endl;

    std::cout << binarySearch(arr, 0, 8, 10) << std::endl;

    return 0;
}

[lastchance]

Gives

1
-1
6

which is correct for searches for 3, 6, 10.

You've now edited your code - that is unhelpful here, since it changes the test cases.

When searching for 5, 6, 10 it gives

2
-1
6

and again that is correct.


Are you sure that you are referring to the same code? You have already changed the version in the original post.

[memepapa]

interestingly, when i run this code with the online compiler here, it returns the correct values

2
-1
6

however, as i run it on my Clion (mac), it gives me

1
32767
32767

[salem c]

$ g++ -Wall -Wextra foo.cpp
foo.cpp: In function ‘int binarySearch(int*, int, int, int)’:
foo.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
   20 | }
      | ^

Your recursive calls don't return the result.
It just falls off the end of the function and you get whatever junk happens to be in whatever register used to return the result.

int binarySearch(int * arr, int low, int high, int key) {
    if(low > high)
        return -1;

    int mid=(low+high)/2;

    if(arr[mid] == key)
        return mid;

    else if(arr[mid]<key) {
        return binarySearch(arr, mid+1, high, key);  //!! return
    }
    else{
        return binarySearch(arr, low, mid-1, key);  //!! return
    }
    
}

The lesson - enable as many warnings as you can.

[lastchance]

#include <iostream>


int binarySearch(int * arr, int low, int high, int key) {
    if(low > high)
        return -1;

    int mid=(low+high)/2;

    if(arr[mid] == key)
        return mid;

    else if(arr[mid]<key) {
        return binarySearch(arr, mid+1, high, key);        // <===== return needed
    }
    else{
        return binarySearch(arr, low, mid-1, key);         // <===== return needed
    }
    
}

int main() {

    int arr[] = {1,3,5,7,8,9, 10, 11, 13};

    std::cout << binarySearch(arr, 0, 8, 5) << std::endl;

    std::cout << binarySearch(arr, 0, 8, 6) << std::endl;

    std::cout << binarySearch(arr, 0, 8, 10) << std::endl;

    return 0;
}

[memepapa]

thanks lastchance,

i am sure it's the same code.

i edited this part

std::cout << binarySearch(arr, 0, 8, 5) << std::endl;
so that instead of searching for 3, it now searches for 5
(because 3 is in position [1] of the array, it returns 1, which may be confused as a boolean result meaning the element is found)
instead, the code is meant to return value of mid, which the position of the found element.

that is why i edited it to search for 5, such that its position (which is 2) would be returned


and i just tried running the same code on my terminal (mac)

instead of
1
32767
32767

it now returns,
1
1
1

instead.

seems like the problem lies with my local machine? both Clion (my IDE) and terminal both gives unexpected return values.

[lastchance]

@memepapa
Please read @salem c's reply (he beat me to it).

What is currently in your OP is undefined behaviour.

[memepapa]

thanks Salem C and lastchance, for being so helpful. I have learned.

one last question,

if it's best practice to write
return binarySearch(arr, mid+1, high, key);

instead of just

binarySearch(arr, mid+1, high, key);

why does it work on the online compiler in this forum?

[salem c]

> if it's best practice to write
If your function returns a result, it's the ONLY way to go.

> why does it work on the online compiler in this forum?
Because despite your best efforts to mess things up, sometimes things just give you the answer you expect.

Your first successful run with one compiler is like reaching base camp on Everest. OK so far, but you have a way to go.

> seems like the problem lies with my local machine?
Nope, just your code.

[lastchance]

It's not just "best practice" - it is required.

why does it work on the online compiler in this forum?

Beginner's luck? To be fair, the online compiler does put a warning triangle in the code area, which draws attention to the possibility of an error. (Note that, where there is multiple branching, this may or may not be a relevant warning; however, in this case it would draw attention to the problem.)

[memepapa]

thanks salem c and lastchance

much appreciated.

[seeplus]

include <iostream>

int binarySearch(const int* arr, size_t low, size_t high, int key) {
	if (low > high)
		return -1;

	const auto mid {low + ((high - low) >> 1)};

	if (arr[mid] == key)
		return static_cast<int>(mid);

	if (arr[mid] < key)
		return binarySearch(arr, mid + 1, high, key);

	return binarySearch(arr, low, mid - 1, key);
}

int main() {
	const int arr[] {1, 3, 5, 7, 8, 9, 10, 11, 13};

	std::cout << binarySearch(arr, 0, std::size(arr) - 1, 5) << '\n';
	std::cout << binarySearch(arr, 0, std::size(arr) - 1, 6) << '\n';
	std::cout << binarySearch(arr, 0, std::size(arr) - 1, 10) << '\n';
}

2
-1
6