How to implement Binary Search algorithm which returns index of the first occurrence of a given value in a sorted array with repeated values.
Classic Binary Search algorithm
The wellknown classic iterative binary search algorithm from the standard JDK works fine for sorted arrays with unique values. Here is its possible implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

Problem
When we feed the algorithm a sorted array with nonunique values, it not necessary returns us an index of the first occurrence of a given key, but one from a range of possible indexes. For instance, the next code returns us 1
.
1 2 

How can we get the first occurrence of a given key without impact on performance?
Solution
Our modified binary search algorithm has got a few simple modifications which apply when we found a given key: we remember found index, decrease the high bound and search again while we have where to search. Finally, if any occurrence found we return one, or return default binary algorithm not found message value, otherwise. Algorithm’s complexity is O(log n).
Here is its possible implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 

and with unit test:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 
