How to implement a lower_bound binary search algorithm in Java?

Question

I want to find a target value 4 firstly appeared place in a sequence [1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6]. when I use java.util.Arrays.binaySearch, it returns index is 9, but I expected 7.

I look java.util.Arrays.binaySearch source code

and I found some comments:

If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

So how to implement a lower_bound binary search algorithm in Java, which returns the target value firstly appeared place.

Note: The lower_bound concept comes from C++, but I don't understand C++ well.

Answer 1

Building on this answer to another binary search question:

How can I simplify this working Binary Search code in C?

This is a search that is equivalent to lower_bound from C++. It returns the number of elements smaller than the value you want to find. That would be the index of the first occurrence, or where one would be inserted if there is no occurrence:

int numSmaller(int[] seq, int valueToFind)
{
    int pos=0;
    int limit=seq.length;
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (seq[testpos]<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    return pos;
}

Note that we only need to do one comparison per iteration.

The linked answer highlights several advantages of writing a binary search this way.