searching an array in C

Question

I'm working on a problem in C, and I have a quick question about it. The problem is as follows: I'm given some sorted array of integers, say, a[i] = { 1, 2, 3, 3, 3 }. Now, I am supposed to run a program that searches for a given integer, returns the location of the first occurrence and the number of occurrences of that integer in the array.

So, if I was searching for 3 then I would have the first occurrence at a[2] and there are three occurrences of 3. For the first, part, of finding the first occurrence, I can simply use strcspn from the string header file. However, for the second part, is there an inbuilt function that would count the number of instances a particular integer?

I can actually do this with my "bare hands" by simply incrementing a counter variable. However, my professor gave me a hint that the return type should be size_t, suggesting some inbuilt functions could be used. Any help would be appreciated.

Thanks, Alexander

Answer 1

No, there is not a standard function for doing this. Your professor said that the return type should be size_t because that is the standard type to use when counting sizes or numbers of objects in memory. The "unsigned int" type might not be large enough on some systems.

Answer 2

Hint: Since the given array is already sorted you can use Binary Search to find an instance of the given integer, walk backwards until you find the first occurence, then increment position until no more matches.

Answer 3

I don't think strcspn is going to help - it works on a string (character array), but you say you have an array of ints. Others have already said what else I was going to say.

Answer 4

Using a variable of size_t as the counter would work. But a better approach is to find one of the instances using a binary search (there is a library function for this) and search forward and backward from there.

Answer 5

Searching for x, you can use binary search to find the first occurence of x and find the first occurance of any integer larger than x (or the end of the array) by using different conditions to set the left and right hand sides of your search window.

A simple binary search in pseudo code:

left,right = 0, n

while right - left > 1
  mid = left + right / 2
  if array[mid] < x
    left = mid
  else
    right = mid

What you need to change here is the if that decides whether to bring the left hand side or right hand side of the search window in. If you have two searches, one to find the left side of the sequence of x-es and one to find the right side, then the difference between these two is the number of entries.