1

How to find index in sorted array where occurs maximum value for the first time?

Let's take for example this array:

1 2 3 4 5 6 7 8 9 ... 200 201 201 201 201 201 201 201 201 201 201 201 201 ...201

where 201 is the maximum value.

Let's say that 201 occurs 200 times in this array. So the answer is that the index equals 200.

The native solution would be to iterate it as long as we get sth that !=201. But I guess that it is possible to find more effective solution. What algorithm do you suggest?

Walter White
  • 51
  • 1
  • 1
  • 9
  • 7
    Why is this tagged as both [tag:java] and [tag:c++]? – Kevin Cruijssen Dec 03 '15 at 15:13
  • Just to clarify, are you trying to get the index of the array where 201 first appears or the total number of times 201 appears? Your statement `Let's say that 201 occurs 200 times in this array. So the answer is that the index equals 200.` makes this unclear. – Calvin P. Dec 03 '15 at 15:18

4 Answers4

2

Binary search is O(log n) which is better than your naïve approach which has a complexity of O(n). In c++, you'd use std::lower_bound.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • And in Java, simple [`Collections.binarySearch`](http://stackoverflow.com/a/15603895/3216312) seems to work... – Petr Dec 03 '15 at 15:17
  • `std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), v.back()));`. – Jarod42 Dec 03 '15 at 16:32
1

Use Binary search.

Native binary search will return any one occurrence of your key. Its "find " criteria is:

if(a[mid]==key)
    return mid;

Make a binary search function where your "find" criteria is:

if(a[mid]==key && a[mid-1]<key)
    return mid;

Also, if its a simple array, you can use a c++ standard template library (STL) function, lower_bound.

vish4071
  • 5,135
  • 4
  • 35
  • 65
1

You can use standard algorithm std::lower_bound declared in header <algorithm>

For example

#include <algorithm>
#include <iterator>

//...    

size_t n = std::distance( std::begin( a ), 
                          std::lower_bound( std::begin( a ), 
                                            std::end( a ), 
                                            *std::prev( std::end( a ) ) ) );

where a is the name of a sorted array.

Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
0

Iterate from the end of the array, not the beginning. The first occurrence of the maximum value is likely to be closer to the end than the beginning.

for (int i = array.length; i >=0; i--) {
     do stuff
}
TangledUpInBlue
  • 746
  • 4
  • 13
  • 2
    Bad solution. Say, my array is: a[100] = {1,2,2,2,2,2....2}. Then, ans is: index 1, and iterating from the end does 99 iterations. – vish4071 Dec 03 '15 at 15:16