1

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.

Improve this question
3
  • 1
    To find the first 4, treat 4 as greater than the target value, and 3 as less than the target value. Don't terminate the algorithm early when a value in the array is 4. Commented Aug 20, 2019 at 17:09
  • 1
    Just iterate backwards until you find a different value, storing the previous index (which you return at the end of the algorithm). Commented Aug 20, 2019 at 17:27
  • 4
    @JacobG. Worst case, that results in an O(n) algorithm, which defeats the purpose of a binary search. Commented Aug 20, 2019 at 17:32

3 Answers 3

Reset to default
3

I think the implementation below will do the job correctly: 

int firstOccurrence(int[] sequence, int x) {
    int min = 0;
    int max = sequence.length - 1;

    int result = -1;

    while (min <= max)
    {
        // find the mid value and compare it with x
        int mid = min + ((max - min) / 2);

        // if x is found, update result and search towards left
        if (x == sequence[mid]) {
            result = mid;
            max = mid - 1;
        } else if (x < sequence[mid]) {
            // discard right half
            max = mid - 1;
        } else {
            // discard left half
            min = mid + 1;
        }
    }

    // return the leftmost index equal to x or -1 if not found
    return result;
}

Edit:

Change the way to compute mid to avoid overflow with larger sums

// Previously, can overflow since we add two integer
int mid = (min + max) / 2;

// Now
int mid = min + ((max - min) / 2);

// Another way using the unsigned right shift operator
int mid = (low + high) >>> 1;
// The left operands value (low + high) is moved right
// by the number of bits specified (2 in this case) by the right operand and
// shifted values are filled up with zeros.
// The >>> treats the value as unsigned
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for your answer, but (min+max)/2 could be overflow.
Can you give me input values with which you get an overflow. By the way you can compute mid like this : mid = min + ((max - min) / 2);
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.

Improve this answer

8 Comments

If all elements in the sequence is greater than valueToFind you will return 0, this is an error, and if all elements in the sequence is smaller than valueToFind you will return length + 1, not a good return value.
If all elements are greater, I will return zero. That is what it's supposed to do. If all elements are less, then I will return length, which is also what it's supposed to do.
And shifting right to do the division is not faster since the compiler will optimize / 2 but cannot do much with bit shifting, and not all programmers will understand this operation.
Shifting to the right is occasionally faster, but /2 also works just fine, even though it cannot be optimized to a shift unless the compiler can figure out that the operand is always positive. The important part of that expression is to avoid overflow
@BSO you just check, of course. The OP asked for an equivalent of C++ lower_bound, and that is what I provided. I also explained exactly what it does an gave it a name that makes it obvious. It turns out that that this contract is also the most convenient and efficient for cases in which you specifically want to search for the position of the first occurrence. Think of some realistic use cases and try it.
|
0

It think it will help you 

public static boolean binarysearch(int[] data, int target, int low, int high){
    if(low>high){
        System.out.println("Target not found");
        return false;}
        else{
                int mid=(low+high)/2;
                if(target==data[mid])
                    return true;
                else if(target<data[mid])
                    return binarysearch(data, target, low, high);
                else
                    return binarysearch(data, target, low, high);
                }
}
Improve this answer

1 Comment

Do you think a person asking how to implement a lower bound in java would benefit from a recursive code instead of iterative one?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.