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

Improve this question
5
  • May I suggest you add the "Homework" tag to this question? Commented 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). Commented 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!). Commented 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. Commented 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. Commented Jan 22, 2010 at 3:41

5 Answers 5

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

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: 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.
@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: 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.
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.
|
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.

Improve this answer

Comments

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.

Improve this answer

1 Comment

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.
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.

Improve this answer

Comments

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.

Improve this answer

1 Comment

Hi David, what library function are you talking about? Thanks,Alex

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.