The answer may not be that simple because "binary search" is not a
completely unambiguous term. More precisely, you have to state what
happens if the binary search is performed on an array which may contain
repeated values: Should the binary search just tell whether the element
exists in the array, or if there's more than one such element, should it
return a handle to the first one in the array?
If "binary search" means "tell me if this element exists in the
array", then the answer of 1 is correct. However, if it means "give me a
handle to the first appearance of this element in the array", then the
correct answer becomes 3 (because the binary search needs to be
continued even if an element with the same value is found immediately).
Even if we are only checking for the existence of the element in the
array, the binary search would require in the worst case 4 comparisons:
the first comparison checks the fourth element, then, assuming that
element is too small, it checks the fifth element (because the middle of
4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is
also too small, it checks the sixth element (which is the middle of 5
and 7), and if that also was too small, finally the seventh.
That is wrong.
If it were element 7,
the binary search pattern would be 4,6,7.
Incrementing from 4 to 7,
just obviously isn't binary search.
/* BEGIN new.c output */
int array[] = {1,2,3,4,5,6,7};
Searching for value 1 in array.
Value 1, found in array[0].
3 comparisons were made.
Searching for value 2 in array.
Value 2, found in array[1].
2 comparisons were made.
Searching for value 3 in array.
Value 3, found in array[2].
3 comparisons were made.
Searching for value 4 in array.
Value 4, found in array[3].
1 comparisons were made.
Searching for value 5 in array.
Value 5, found in array[4].
3 comparisons were made.
Searching for value 6 in array.
Value 6, found in array[5].
2 comparisons were made.
Searching for value 7 in array.
Value 7, found in array[6].
3 comparisons were made.
/* END new.c output */
/* BEGIN new.c */
#include <stdio.h>
#define NMEMB(A) (sizeof(A) / sizeof *(A))
int Comps;
void *b_search(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
int comparison(const void *arg1, const void *arg2);
int main(void)
{
int array[] = {1,2,3,4,5,6,7};
const int target[] = {1,2,3,4,5,6,7};
unsigned index;
int *found;
puts("/* BEGIN new.c output */\n");
puts("int array[] = {1,2,3,4,5,6,7};\n");
for (index = 0; index != NMEMB(target); ++index) {
Comps = 0;
printf("Searching for value %d in array.\n", target[index]);
found = b_search(target + index, array, NMEMB(array)
, sizeof*array, comparison);
if (found != NULL) {
printf("Value %d, found in array[%u].\n"
"%d comparisons were made.\n"
, target[index]
, found - array, Comps);
} else {
printf("Value %d, not found in array.\n"
"%d comparisons were made.\n"
, target[index], Comps);
}
putchar('\n');
}
puts("/* END new.c output */");
return 0;
}
void *b_search(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int comp;
size_t middle, high, low;
const unsigned char *array, *found;
found = NULL;
if (nmemb != 0) {
array = base;
low = 0;
high = nmemb;
do {
nmemb = high - low;
middle = nmemb / 2 + low;
base = middle * size + array;
comp = compar(key, base);
if (comp > 0) {
low = middle;
} else {
high = middle;
if (comp == 0) {
found = base;
break;
}
}
} while (nmemb != 1);
}
return (void *)found;
}
int comparison(const void *arg1, const void *arg2)
{
++Comps;
return *(const int *)arg2 > *(const int *)arg1 ? -1
: *(const int *)arg2 != *(const int *)arg1;
}
/* END new.c */