recursion binary search

[encoded]

I had to change this from a binary search to recursive binary search. I had the
binary up and going fine. What I have(had) is to search out 45. The list is that, a list[], then the length of the list, 10. Finally the item, 45. I know I'm it's probably something relatively simple. Just not sure what. Any pointers anyone ?

header.h file
template<class Type>
int binarySearch(const Type list[],Type length, const Type& item){

	int first = 0,
		last = length - 1,
		mid;
	bool found = false;
	
	if (first <= last){ // first check to see it it needs to go any further.
		return -1;
		mid = (first + last) / 2;

		if(list[mid] == item) // if found item, 45.. true if so
			found = true;
		
		else if (list[mid] > item)
			return  binarySearch (list, mid -1, item) ; //passing the list, mid, and item - which is 45. for bottom/lowwer  list
		else
			return binarySearch (list, mid + 1,item);   //passing the list, mid, and item - which is 45. for top/higher list

	/*if(found)
		return mid;  // just left over from binary part. should not be needed, ( i wouldn't think)
	else
		return -1;*/

	}//end if's
}//end binarySearch
________________________________________________________________________________
main.cpp file

#include <iostream>
#include "binarySearch.h"
using namespace std;

int main(){
	
	int intList[] = {2, 16, 34, 45, 53, 56, 69, 70, 75, 96}; // list of 10 integers with 45 in "middle"
	int pos;

	pos = binarySearch(intList,10,45);  // length is 10, item is 45
	if(pos != -1)
		cout << "Line 5: " << 45
		<< " found at position "
		<< pos << endl;
	else
		cout << "Line 7: " << 45
		<< " is not in intList " << endl;

	cin.sync();
	cin.peek();
}

[slicedpan]

Firstly:

if (first <= last){ // first check to see it it needs to go any further.
		return -1;

should be
if (first <= last) return -1;
make sure to delete the closing brace at the bottom as well. atm your function will always return -1.
Also your function never returns a proper value. the only return statement that actually returns a value is the return -1 at the start but that should only be when the number you are looking for is actually not in the list.

return binarySearch (list, mid + 1,item);   //passing the list, mid, and item - which is 45. for top/higher list 

This line is also incorrect. In your example this would actually pass the first 6 elements of the array to the function, when it should be passing the last 5.

[encoded]

ok, revamped code, but now getting a "Line 5: 45 found at position 4" since this is a 0 based array, it should be position 3, correct ? I don't see my error. Could someone enlighten me to where I am not calculating this correctly,..please. Greatly appreciated ! Regards

template<class Type>
int binarySearch(const Type list[],Type length, const Type& item){

	
	int first = 0,
		last = length - 1,
		mid=0;
	bool found = false;

	if(list[mid] == item){ // if found item which is 45. = true if so
		return mid;
		found = true;}
	
	if(first > last)// first check to see it it needs to go any further.
		return -1;

	if (first <= last) // create a mid point to search
		mid = (first + last) / 2;

	else if (list[mid] > item)
		return  binarySearch(list, mid - 1,item ); //passing the list, mid, and item - which is 45. for bottom/lowwer list
	else
		return binarySearch(list, mid + 1,item);   //passing the list, mid, and item - which is 45. for top/higher  list
	
}//end binarySearch 

[slicedpan]

A bit closer now. That bool found does absolutely nothing as far as i can see since the line
found = true;
will never be reached because it is just after a return statement.

You still haven't changed the line:
return binarySearch(list, mid + 1,item);
and this is why your program is not returning the right result. What you want this line to do is to call binarySearch starting 1 beyond mid, until the end of the array.

For example take the original array:
int intList[] = {2, 16, 34, 45, 53, 56, 69, 70, 75, 96};
Let's say you were looking for 75. When you call binarySearch, your function will find the midpoint of the array (56) and compare it to 75. Obviously 75 is higher so we need to take the second half of the array into consideration. At the moment the function call will be:
binarySearch(list, 6, 75);
This means that it will take the first 6 items of the original array to check. Obviously 75 isn't there so it won't work. Have a think about how you can change it so that the right elements get passed to the function

[encoded]

Thanks mate ! your a life saver : ) really appreciate the help more than you know!
this is working and what the final result is...

template<class Type>
int binarySearch(const Type list[],Type length, const Type& item){

	int first = 0,
		last = length - 1,
		mid=0;
	//bool found = false;   // not really needed at this point

	 if (first < last) // create a mid point to search
			mid = (first + last) / 2;

	if(list[mid] == item){ // if found item which is 45. = true if so
		return mid;}
	
	if(first > last )// first check to see it it needs to go any further.
		return -1;

	else if (list[mid] > item)
		return  binarySearch(list, last - 1, item); //passing the list, mid, and item - which is 45. for bottom/lower list
	else
		return binarySearch(list, first + 1, mid );   //passing the list, mid, and item - which is 45. for top/higher list
	
}//end binarySearch 

[slicedpan]

er... I'm glad this is working, but your function still isn't right. You're now checking the first (1) element of the array not for 45 , but for mid, which would be equal to 6, what you want is:

return binarySearch (list + mid + 1, length - mid,item) + mid + 1;

what this does is it passes an array that starts 1 after the number at the midpoint and includes all the elements up till the end, and searches for the same number that was passed the first time. You also have to add +mid +1 at the end, since this new function will label the array from 0, even though that zero really corresponds to the point after the midpoint. Try your function first with the other numbers in the array, and you should find that it is not getting the correct answer. Then swap it for the line above and see if you can figure out how it works.

[encoded]

well again, thank you for your help. I tried return binarySearch (list + mid + 1, length - mid,item) + mid + 1; and it gave me "found 45 at position 14" so I will have to play with this piece of code to complete understand. Your time and effort to help me is greatly appreciated. I need a lot practice and time under my belt for this language. Self teaching for a grade under strict time limits does not let things absorb/understand at this point. LOTS of practice yet <sigh>

[slicedpan]

No problem, here's the complete code i came up with, try it and it should work right. See if you can figure out where it differs from yours.

template<class Type>
int binarySearch(const Type list[],Type length, const Type& item){

    int mid;

    if (length = 0) return -1;
    mid = (length - 1) / 2;

    if(list[mid] == item) // if found item, 45.. true if so
        return mid;

    else if (list[mid] > item)
            return  binarySearch (list, mid -1, item) ; //passing the list, mid, and item - which is 45. for bottom/lowwer  list
    else
            return binarySearch (list + mid + 1, length - mid,item) + mid + 1;   //passing the list starting at mid + 1 and item - which is 45. for top/higher list
}

using namespace std;

int main(){

	int intList[] = {2, 16, 34, 45, 53, 56, 69, 70, 75, 96}; // list of 10 integers with 45 in "middle"
	int pos;

	pos = binarySearch(intList,10,96);  // length is 10, item is 45
	if(pos != -1)
		cout << "Line 5: " << 45
		<< " found at position "
		<< pos << endl;
	else
		cout << "Line 7: " << 45
		<< " is not in intList " << endl;

}