Recursive Binary Search C++

*** Comment ***

This code works fine, but I have a question about how binary_search works.

I understand that the array or vector needs to be sorted out, and that if the target value, x , is bigger than the middle value, the program looks at the right side of the array, and if smaller, we look at the opposite side of it.

*** Question ***
Does this mean that if our target value is less than the middle value of the array, then the binary search fails, and it returns something like -1 ?

*** Reasoning ***
To me this does not make sense. The binary search needs to keep going until it finds the target value, but for this code this does not happen. Take a look at the output.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int binary_search(const vector<int>& v, int x, int begin, int end){
	if(begin >= end){ return -1;}
	else {
		int mid = (begin + end) / 2;
		if (x == v[mid]){ return mid;}
		else if(x < v[mid]){ return binary_search(v, x, begin, mid);}
		else if(x > v[mid]){ return binary_search(v, x, mid + 1, end);}
	}
	return 1000;
}

int binary_search(const vector<int>& v, int x){
	return binary_search(v, x, 0, v.size());
}

int main(){
	vector<int> v = {80, 68, 50, 45, 30, 20, 10};
	int target = 50;
	if (binary_search(v, target, 0, v.size()) == -1){
		cout << "Range is empty! -1 returned!" << endl;
	}
	else{
		cout << "Inde ox binary_search() is: " << binary_search(v, target, 0, v.size()) << endl;
	}
}


Note: if target = 50, it returns -1, but if it is exactly the middle value in the vector, then it returns the index of middle value. Why this happens ? Why there is no index for 50, and instead -1 ? (This is not what I expected recursive binary search do).
Last edited on
Because the data is not sorted.

*** Question ***
Does this mean that if our target value is less than the middle value of the array, then the binary search fails, and it returns something like -1 ?


No, that should only happen if the target is not is data set.

You can see where it goes wrong by using a debugger. Or a poor person's debugger by putting std::cout statements to print values.

Ideally your ints should be std::size_t because that is what is used for subscripts in STL containers. It doesn't make sense to have a negative value there.
best sort the data

#include <algorithm>

then after your vector put the lines

std::sort(v.begin(), v.end());

for(auto it : v){
std::cout << it << " ";
}

to show sorted vector

Then give that a go.
@TheIdeasMan,

So you mean that this is not the right way my recursive binary search is implemented ?
I think it should always look for the index of the target value, which it does not because it returns -1.

Am I right ?


@jamesfarrow,

Yes you are right. It is easier for me to implement the whole binary search process using for loops or for each loops with vector sort. However, I am trying to learn the recursive way of doing it using the concept of recursion in C++.
So you mean that this is not the right way my recursive binary search is implemented ?

Your search is correct except it assumes that the input is sorted in ascending order, but your vector is sorted in descending order.

See:
http://coliru.stacked-crooked.com/a/eaa1c84e57b6f0c1
Last edited on
Topic archived. No new replies allowed.