tl;dr:
you might want to check your test code that calls the Search function - maybe the error is also there!
Long version:
This is not a stand-alone solution, but simply a verification for solution1. I'm only using the solution form for the sake of code formatting:
Using this test code, I could verify that solution 1 is correct:
#include <iostream>
using std::cout;
using std::endl;
int Search(int target, int* start, int* tail){
if(start>tail){
cout<<"not find"<<endl;
return -1;
}
int offsetMid= (tail-start)/2; cout<<"offset: "<<offsetMid<<" mid " <<*(start+offsetMid)<<endl;
cout<<start<<" " <<tail<<endl;
if(target == *(start+offsetMid) ){
cout<<"mid"<<endl;
return (offsetMid+1);
}
if(*(start+offsetMid) > target){
cout<<"left"<<endl;
tail = start+(offsetMid-1);
return Search(target, start, tail);
}
if(*(start+offsetMid) < target){
cout<<"right"<<endl;
start = start+(offsetMid);
return Search(target,start , tail);
}
}
void test_Search() {
int arr[] = {2, 5, 6, 14, 44, 51, 94, 221, 356, 444};
int* start = arr;
size_t length = sizeof(arr)/sizeof(int);
cout << length << endl;
int *end = start + length;
int s = Search(6, start, end);
cout << s << endl;
}
This produces the output:
10
offset: 5 mid 51
0033FA60 0033FA88
left
offset: 2 mid 6
0033FA60 0033FA70
mid
3
Note how in the test function I calculated the end address of the array by explicitely dividing the size of the array by
sizeof(int)
. This is necessary, because adding a number to an
int
pointer imlpicitely multiplies the address offset by
sizeof(int)
: Suspect that may be the reason why you could not reproduce the expected results when following the advice from solution 1.
P.S.: The compiler complained with the following warning which I did not bother to fix - but you should:
Quote:
warning C4715: 'Search' : not all control paths return a value
It's easy enough to spot, but if you don't, here's a tip: what will happen if you search in the above array for, say, the value 11?