int my_rand(void)
{
return rand() % 371;
}
int find_first_linear(int *arr, int sz, int item)
{
for(int i = 0; i < sz && arr[i] <= item; ++i)
if(arr[i] == item) return i;
return -1;
}
int find_first_binary(int *arr, int sz, int item)
{
int lo = 0, hi = sz - 1, firstfound = -1;
while(lo <= hi) {
const int mid = (lo + hi) >> 1;
const int m = arr[mid];
if(m < item) {
lo = mid + 1;
} else {
if(m == item) firstfound = mid;
hi = mid - 1;
}
}
return firstfound;
}
int main()
{
srand(42);
const int bufsize = 1711;
int buf[bufsize] = {0};
int *v = &buf[0];
for(int test_count = 4000; test_count--;) {
const int arrsize = 8 + rand() % (bufsize - 8);
const int item = my_rand();
generate(v, v + arrsize, my_rand);
sort(v, v + arrsize);
const int expected = find_first_linear(&v[0], arrsize , item);
const int actual = find_first_binary(&v[0],arrsize , item);
if(expected != actual) {
cout << "An error occured" << endl;
cout << "Search item: " << item << endl;
cout << "Size: " << arrsize << endl;
cout << "Sample: " << buf << endl;
exit(-1);
}
}
cout << "Äll test cases passed and no infinite loop detected" << endl;
}