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

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.

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

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.

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.

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.

Similar Questions

I want to understand more about binary searching, cause I don't really understand. Binary search requires a precondition that an array is sorted. I got that right? It seems like a method should check

i came across an interview question which asks while searching a value in an array using 2 perallel threads which method would be more efficent (1) read each half of the array on a different thread

Basically: Fast, sorted insert. Returns position of where an item would be inserted if it's not found in the data structure. An array with binary search satisfies my second requirement, but it's sti

You are given an 2D array of MxN which is row and column wise sorted. What is the efficient way to search for an element?

In c++, std::set which stores its element in sorted order can insert elements in O(log n) time. But all the methods i know take linear time: Inserting the element at the end of the array and swapping

Given a Sorted Array which can be rotated find an Element in it in minimum Time Complexity. eg : Array contents can be [8, 1, 2, 3, 4, 5]. Assume you search 8 in it.

I have this array (shortened for readability) array(10) { [0] => array(23) { [account_id] => int(4294967295)[player_slot] => int(0)[hero_id] => int(41)[item_0] => int(0)[item_

Total newbie here, having problems searching a 2 dimensional array. I have a 3x3 char array that holds '1' thru '9' like a tic tac toe board. For testing, I hard coded it to search for a '5', hoping i

I'm to write an event based simulator in C#. I need a sorted container for the scheduler that has the following capabilities: Key - Value pairs are stored sorted by the key (Time, Delegate pairs) Eff

Given a sorted array of integers, how can we find a pair of integers that sum to K? e.g. array = 1,3,5,6,0, K = 6, the answer is 1 and 5. Time complexity should be minimized.

I'm attempting to bubble sort an array, then output the original and the sorted. It seems to work, but when it outputs the data, it outputs [l@486f03ec as both arrays instead of numbers. I don't know

Can I do a foreach on a function that takes an array object and sorts it. I know I can do a dependent observable, but I have an array of an array coming from the mapping plugin. foreach: sortList($arr

I have some problem with removing an element from a sorted array (all instances of an element must be removed). When I run my program, I get a segmentation fault. I have no idea why that happens, beca

I want to implement an algorithm that inserts sorted arrays into binary search trees but I don't want ending up with a tree that only grows to one side. Do you have any ideas? Thanks.

I want to convert a sorted integer array into a binary search tree. I believe I understand how to do this. I have posted my pseudo-code below. What I cannot picture is how the recursion actually works

I have this multidimensional array. I need to search it and return only the key that matches the value of the slug. I know there are other threads about searching multidimensional arrays, but I'm no

I have three sorted array I need to find top five 5 element from these array .I am able to find first two element largest element .how I will find other ? can you suggest how we can find other 3 ele

How do I put values from a sorted list and array into a dictionary and determine how many time numbers repeat themselves? This is my code so far. from numpy import * from random import * lista=[] for

Given an integer k and an sorted array A (can consist of both positive and negative numbers), output 2 integers from A such that a-b=k in O(n) time and O(1) space O(n logn) Solution: Traverse the arr

We have given an array of n integers of which first n-(squareroot)n elements are sorted (it means (root)n elements from the last are not sorted). We have to sort the entire array with minimum time com

I just want to obtain the key by searching with the value id_img=17. This is the array: $array_test = array ( 0 => array(id_img => 18, desciption => Super image, author => Person

I am writing an easy program the just returns true if an array is sorted else false and I keep getting an exception in eclipse and I just can't figure out why. I was wondering if someone could take a

I have the following already sorted data: AAA AAA TCG TTT TTT TTT I want to count the occurrence of each string yielding AAA 2 TCG 1 TTT 3 I know I can do that with uniq -c, but here I need to do

I need a generic container that keeps its elements sorted and can be asked where (at which position) it would insert a new element, without actually inserting it. Does such a container exist in the .N

Suppose given an array of size n, with sorted values. In iteration i, a new random-generated value is given, and inserted into the end of the array. The array is then resorted, and discard the least

I am new to C and was writing a function to insert an element to sorted list. But my code does not display the last digit correctly. Though i know there are variety of ways to correct it but i want to

Possible Duplicate: In-place array reordering? I have original unsorted array with structures such as: {D, A, B, E, C} and array of indexes of original array in sorted order: {2, 3, 5, 1, 4} // Edi

This question already has an answer here: Java Array, Finding Duplicates 8 answers If I initialise an array of person objects with this data myPeople[0] = new Person(Alice, Foo, 22 ); myPeo

I've been working on search function that will let me group specific words then recursively search for them in an array and I've coded myself into a hole I think. This is my first foray into recursion

While preparing for tech interview I stumbled upon this interesting question: You've been given an array that is sorted and then rotated. example Let arr = [1,2,3,4,5] which is sorted and then rotated

I was preparing for a competition and came across this question, which I can't comprehend. Consider a set of 'n' elements in an array, which is sorted except for one element that appears out of order.

My teacher gave me the next task: On a sorted array, find the number of occurrences of a number. The complexity of the algorithm must be as small as possible. This is what I have thought of: public s

I'm working on a problem where I'm given a sorted array of integers, and I am supposed to take an input from the user, search for the input, and return the first instance of that input (if it exists)

Is there any way to maintain a sorted array of objects? For example, if I have an object with properties ID, Date, Name and a collection of these objects: $col = array(); public function addNewObject(

I am trying to build a program that accepts an array of integers as parameter and return a string. The string would be ascending if the array is sorted from the smallest to the greatest, descending

I have an array whose keys are in the format [A1] -> [A20], [B1] -> [B20], etc, and I'm trying to sort that array using first ksort() (to get the letters in the correct order) and then uksort().

the question is simple: there is some way that the ordered array that returns me the qsort, is returned in reverse, ie I want to avoid the use of any auxiliary array to invest the resulting array us

Given a sorted array of integers, can we build a sorted array of the sums of all pairs in O(n^2)? A trivial solution would be to build the array of sums in O(n^2) and then to sort it in O(n^2 (log(n^2

I want to create an almost sorted array, as efficiently as possible (to explore effect of random subtle variations in a list, I expect to call this routine a lot). I have Ruby code which does what I

I tried to sort using sorted dir =[A1,A2,A10,A3] sorted(dir) My expected array is [A1,A2,A3,A10] but actual result is [A1, A10, A2, A3] How to sort array by name in python ?

I have ProperyGrid loaded with categorised PropertySpec and set to CategorizedAlphabetical sort. When form runs categories then items within categories are sorted. An annoying artefact is that Propert

I have a PHPArray : $fullData = array ( array ( 'id' => 23123, 'name'=>'a', number =>...), array().... ); This full dataset is displayed to the user. However if he comes from a form page, I

Let's say we have this sorted array 0 1 1 1 1 2 2 2 2 2 3 10 10 10 I would like to find efficiently the positions where an element changes. For example in our array the positions are the following:

Problem: Given a sorted array of integers find the most frequently occurring integer. If there are multiple integers that satisfy this condition, return any one of them. My basic solution: Scan throu

I am looking for a solution similar to Google's Did You Mean: Word I have an array of vehicles entered as 2011ChevroletMalibu 2011FordF150 2009FordProbe etc... In my app I have three Textfields. Y

I have an array of sorted integers, and I'd like to get the two consecutive indices of elements that bound a particular value I pass in. To illustrate, because it's hard to describe in words, let's sa

I came across an algorithmic puzzle as following: Given an array of events in the form of (name, start time, end time) e.g. (a, 1, 6) (b, 2, 4) (c, 7, 8) ... The events are sorted based on their start

I have the following code: //data_r is an array with values var i = 0; var sort_order = new Array(); data_r.sort(function (a,b) { var res = a[0] - b[0]; sort_order[i] = res; i++; return res; }); In t

I have a hashmap, I wish to get an array of the values in this hashmap, but I wish for the array to be sorted by the keys in the hashmap. For instance if the map looks like this: <2,obj1> <4

I have to make a program in Java to create a sorted array in descending order. When i try to insert 10, 3 it is ok, but when i insert 10, 3, 8 the result is 10, 8, 0. For some reason the 0 appears on