Yes, I meant "two parameters for where you're searching", you obviously also need whatever you're searching for - unless you have telepathic code [and my telepathic code usually works very poorly - just like own telepathic abilities].
--
Mats
Printable View
Yes, but matsp was referring to that besides item, you need to pass first and last!
Ok, I THINK I have written the code as described by mats algorithm, however, I am not finding any numbers in the list (whether they are there for real - not telepathically (that was for you mats) or not!
I have to be missing something, but ...what? My eyes are blurry and I almost can't see my laptop let alone a missing code statement. or something more subtle than that.
Sorry, I am getting punchy again!
Here is the piece of work (it's not art anymore):
Code:template<class elemType>
int orderedArrayListType<elemType>::binarySearch(const elemType& item)
{
int first = 0;
int last = length - 1;
return binarySearchImpl(item, first, last);
}
//Function written for Test 5 Question 22
template<class elemType>
int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)
{
if(first >= last)
return -1;
int mid = (first + last) / 2;
if(list[mid] == item)
return mid;
if (list[mid] > item)
return binarySearchImpl(item, mid + 1, last);
else
return binarySearchImpl(item, first, mid - 1);
}//end binarySearch
That's probably my fault - I got the last/first mixed up in my pseudo-code. If array[mid] > item you should, obviously search between the "first and mid" - so just swap your > with a < in the if-statement deciding which half of the array to search.
--
Mats
Code:if(list[mid] > item)
last = mid - 1;
else
first = mid + 1;
:) So yes, a little mistake, like matsp points out.Code:if (list[mid] > item)
return binarySearchImpl(item, mid + 1, last);
else
return binarySearchImpl(item, first, mid - 1);
Reverse the if, so it looks like the original algorithm.
I found that TOO!
I will retype and see what I get.
Hang tight!
NOPE! It still says the number isn't found in the list!
Here is the call to the function in the driver: (I have this same code for two different lists in the driver program)
And here are the functions retyped as discussed:Code://using binarySearch function
cout << "Enter a number to find in the list: ";
int x;
cin >> x;
if(intList.binarySearch(x) == -1)
{
cout << "The number " << x << " was not found in: ";
intList.print();
cout<<endl;
}
else
{
cout << "The number " << x << " was found in: ";
intList.print();
cout << "at position number: " << intList.binarySearch(x + 1) << endl;
}
On the first pass I get number was found but with a -1 returned as the position.Code:template<class elemType>
int orderedArrayListType<elemType>::binarySearch(const elemType& item)
{
int first = 0;
int last = length - 1;
return binarySearchImpl(item, first, last);
}
//Function written for Test 5 Question 22
template<class elemType>
int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)
{
if(first >= last)
return -1;
int mid = (first + last) / 2;
if(list[mid] == item)
return mid;
if (list[mid] > item)
return binarySearchImpl(item, first, mid - 1);
else
return binarySearchImpl(item, mid + 1, last);
}//end binarySearch
On the second pass I get the number wasn't found.
You are searching for x+1 when you print the number. So if you enter 4, is 5 also in the list?Code:intList.binarySearch(x + 1)
--
Mats
Yes! The numbers I enter are consecutive and I use the middle values in the list. But, let me put that back to 'x' and see what happens.
It's a good thing I like coffee.
Do
Instead. Just an optimization.Code:int pos = intList.binarySearch(x)
if (pos == -1)
// not found
else
cout << pos; // found
I'll try that!
It will also avoid your subtle bug since pos is the index in the array it's stored, you won't have to call the binarySearch function a second time to find the position.
YAHOOO!!!!! YAHOO!!!!! You did IT!
That made it all better!
It works. I can't believe it, I am soooooooo HAPPY!
If it were earlier I'd be singing in a beer!
Well, probably not, I'd be working on more CODE!
But I think that did it, I will try a few more tests, and get back to you!
Matsp made the inital discovery of your subtle bug.
I danced the JIG too fast.
When I enter a number in the middle of the list on the first pass it finds it. When I look for a number that is the lower or upper limit on the first pass it doesn't find it. And the second call to the function doesn't find any number.