Finding a sorted array in C

Question

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

So, if I were looking for 3 , then I would have the first occurrence in a[2] , and there are three occurrences of 3 . For the first part of searching for the first occurrence, I can simply use strcspn from the line header file. However, for the second part there is a built-in function that will count the number of instances of a certain integer?

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

Thank you, Alexander

Answer 1

No, there is no standard feature for this. Your professor said that the return type should be size_t, because it is the standard type used in calculating the size or number of objects in memory. The unsigned int type may not be large enough for some systems.

Answer 2

To search for x, you can use a binary search to find the first occurrence of x and find the first fill of any integer greater than x (or the end of the array) using various conditions to set the left and right sides of the search box.

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 if it decides whether to bring the left side or the right side of the search box. If you have two searches, you can find the left side of the x-es sequence and one to find the right side, then the difference between the two is the number of entries.

Answer 3

Tip . Since this array is already sorted, you can use Binary Search to find an instance of a given integer, go back until you find the first occurrence, and then increase the position until there are no more matches.

Answer 4

I don't think strcspn will help - it works with a string (an array of characters), but you say you have an array of ints. Others have already said what else am I going to say.

Answer 5

Using the variable size_t as a counter will work. But the best approach is to find one of the instances using binary search (there is a library function for this) and search back and forth from there.