2

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

5
  • May I suggest you add the "Homework" tag to this question?
    – GreenMatt
    Jan 22, 2010 at 3:35
  • 1
    I don't think that the type being size_t suggests that a library function should be used. size_t should always be used when returning lengths of things (including the number of elements meeting some criteria in an arbitrarily sized array).
    – Trent
    Jan 22, 2010 at 3:36
  • Hey GreenMatt, I tried doing that as well, but the tag wouldn't work. Ezod thankfully added it on there (Thanks!).
    – Alex
    Jan 22, 2010 at 3:38
  • 2
    How's strcspn going to help you with an int array? Just because of size_t, you went poking around in the header files? size_t is an integral type in C which can't be negative: that's why your professor suggested size_t instead of int. Your count can only be >= 0. Jan 22, 2010 at 3:38
  • Alok, I thought that size_t could only be the return type of an a library function, but yah, that wasn't the best reason to do so, as you pointed out.
    – Alex
    Jan 22, 2010 at 3:41

5 Answers 5

5

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.

6
  • size_t isn't completely the right type for counting elements, either; it counts (byte) sizes. Compare with ptrdiff_t which counts distance in number of elements, or uintptr_t which only counts in one direction. On the other hand, I don't think I've seen a system in practice where those types have different underlying representation than ssize_t and size_t...
    – ephemient
    Jan 22, 2010 at 3:53
  • @ephemient: I would disagree about counting bytes only. How would you explain the nmemb parameter to fread/fwrite/calloc for example? They're of size_t type. Also: qsort/bsearch. Jan 22, 2010 at 4:03
  • @Alok: So you think the standard library is a good reference guide? Wow… ;-) Yes, it is certainly true that size_t and ssize_t are frequently used for counting elements instead of bytes. I still hold the opinion that uptrdiff_t and ptrdiff_t match that intention better.
    – ephemient
    Jan 22, 2010 at 4:32
  • @ephemient: if you're saying that you want to use *ptrdiff_t for indexing, I can agree with you. If you are saying that it's more logical to use these types for counting in general, I would like to disagree. You might not be saying that, though, which I hadn't realized earlier. Jan 22, 2010 at 5:00
  • I mean to say that a uptrdiff_t return type would also make sense, although practically there isn't any gained or lost value in doing so over size_t.
    – ephemient
    Jan 22, 2010 at 5:54
2

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.

1

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.

1
  • 4
    If you use binary search, you are not guaranteed to land on the first occurrence. You may well end up in the middle of the range - you'll have to search in both directions. Jan 22, 2010 at 3:42
0

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.

0

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.

1
  • Hi David, what library function are you talking about? Thanks,Alex
    – Alex
    Jan 22, 2010 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.