CODEWITHSUNDEEP
javaalgorithmbinary-search
douyu
douyu

Reputation: 2599

How to implement a lower_bound binary search algorithm in Java?

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.

Upvotes: 1

Views: 2079

Answers (3)

Ijlal H
Ijlal H

Reputation: 79

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);
                }
}

Upvotes: 0

Ben Souchet
Ben Souchet

Reputation: 1532

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

Upvotes: 3

Matt Timmermans
Matt Timmermans

Reputation: 59174

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.

Upvotes: 1

Related Questions