Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to worst-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound. std::lower_bound
will return the "iterator" (pointer in C, call it const int* res
) to the first matching element (with value N
). If there is no such, we will have N != *res
. If the pointer is correct, perform std::upper_bound
and the count of matching elements will be simply the difference between the result of std::upper_bound
and std::lower_bound
. Also, what comes to API, I suggest you insert the value of zero to count
whenever there is no match. Putting all pieces together, you may obtain something like this:
#include <stdio.h>
static const int* upper_bound(const int* begin,
const int* end,
const int value)
{
size_t count;
size_t step;
const int* iter;
count = end - begin;
while (count > 0)
{
iter = begin + (step = (count >> 1));
if (*iter <= value)
{
begin = iter + 1;
count -= step + 1;
}
else
{
count = step;
}
}
return begin;
}
static const int* lower_bound(const int* begin,
const int* end,
const int value)
{
size_t count;
size_t step;
const int* iter;
count = end - begin;
while (count > 0)
{
iter = begin + (step = (count >> 1));
if (*iter < value) /* upper_bound compares "*iter <= value" */
{
begin = iter + 1;
count -= step + 1;
}
else
{
count = step;
}
}
return begin;
}
void get_number_of_ints(const int* array,
size_t array_length,
int target_value,
size_t* first_index,
size_t* count)
{
const int* iter1;
const int* iter2;
iter1 = lower_bound(array, array + array_length, target_value);
if (*iter1 != target_value)
{
/* No match. */
*count = 0;
return;
}
iter2 = upper_bound(array, array + array_length, target_value);
*first_index = (size_t)(iter1 - array);
*count = (size_t)(iter2 - iter1);
}
int main()
{
int N; /* input variable */
int arr[]={1,1,2,3,3,4,4,4,4,5,5,7,7,7,7,8,8,8,9,11,12,12}; /* sorted */
size_t r = sizeof(arr)/sizeof(arr[0]); /* right bound */
size_t first; /* first match index */
size_t count; /* total number of matches */
/* prompts the user to enter input */
printf( "\nPlease input the integer you would like to find.\n" );
scanf( "%d", &N );
get_number_of_ints(arr, r, N, &first, &count);
if (count == 0)
{
printf("%d not found!\n", N);
}
else
{
printf("%d found at %zu, length %zu.\n", N, first, count);
}
return 0;
}