10

1

I'm studying for a test, and found this question.

You are given a sorted array of integers for example:

```
{-5, -5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99}
```

Write a method:

```
Public static int count (int[] a, int x)
```

that returns the amount of times, number 'x' is in the array.

for example:

```
x = -5, it returns 2
x = 2, it returns 5
x = 8, it returns 0
```

I need to write it as efficient as possible, please don't give me the answer (or write it if you wish, but I won't look), my idea is to do a binary search, and then go both edges (backward and forward) of the value that I find and with the index numbers, return the correct answer, my questions are:

- is it the most efficient way?
- won't it be O(n) in the worst case? (when the array is filled with a single number) -

If so - then why should I do a binary search?

8@ambigram_maker it would probably be a "modified" binary search where if you find your key, you still keep searching. – C.B. – 2014-04-02T14:33:00.077

If you are allowed to do so, check whether the number is present in the array. If not, return. Otherwise, I'd say use premature return to exit the method as soon as possible. – blueygh2 – 2014-04-02T14:33:09.707

there must be a way below O(n), it's a question about complexity, they won't give me a question that I can just go O(n) times and count the number when I find it, it's a twist of binary search in my opinion. – Seth Keno – 2014-04-02T14:33:29.877

2@SethKeno obviously your algorithm has to look at every element in the array. I don't think it gets better than O(n). The naive approach i can think of would rather be O(n^2) [for each element, look at it, then go through the array, counting that element] – fstd – 2014-04-02T14:34:27.893

@SethKeno, for a test the trivial solution is

`O(n)`

and your solution is also`O(n)`

in the worst case. – Anthony Accioly – 2014-04-02T14:36:06.667@fstd what about if I do a binary search, find the number, go backwards until I find a different number, and go forward until I find a different number (or array ends each direction), will it be less than O(n) or not? – Seth Keno – 2014-04-02T14:36:19.727

@user432 and how do you find where the 'next' element is, without going over it linearly? – fstd – 2014-04-02T14:36:35.423

@SethKeno I'm not sure what you have in mind, but note that the big-O notation specifies an

upperbound of the complexity. Your algoritm, even if it on average might outperform the linear solution, sounds still like O(n) to me – fstd – 2014-04-02T14:38:18.590@fstd why is the naive approach O(n^2)? it is sorted – Seth Keno – 2014-04-02T14:38:21.227

@SethKeno the naive approach would have a loop going over the array, and for each (not yet seen) element, it would again go over the array (i.e. two nested loops of complexity O(n) -- that's O(n^2). EDIT: admittedly it wouldn't have to go over the

entirearray all the time, but it still qualifies as O(n^2) (beause it's an upper bound, as said) – fstd – 2014-04-02T14:40:10.7932@fstd Have you read the question? Even the most naive implementation (counting the # of occurences of ONE value in an array is no more than O(n)! And given that the array is sorted, this can certainly be solved in O(log(n)) using some divide and conquer approach. – Gyro Gearless – 2014-04-02T15:03:49.023

@GyroGearless I originally misread the question, as is evident in the comments of a different answer. Forgot to update this thread. (I originally read the question as if the goal was to get the frequency of /all/ distinct members in the array) – fstd – 2014-04-03T15:04:55.147

possible duplicate of Using Binary Search with sorted Array with duplicates

– nawfal – 2014-06-15T20:08:28.343