CODEWITHSUNDEEP
javaalgorithm
farm ostrich
farm ostrich

Reputation: 5989

For a binary search where the element isn't found, how to return the index it should be inserted into

I'd like to use a binary search to find the array index that an element should be placed at. This for the purposes of inserting the element into the array while moving down larger elements. How could this binary search be modified to specify the location that non-found elements should be placed at?

    int binarySearch(int arr[], int x) {

        int low = 0;
        int mid = 0;
        int high = arr.length - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (x < arr[mid]) {
                high = mid - 1;
            } else if (x > arr[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        //This is what im trying to get to work
        if (x < arr[mid]) {
            return high;
        } else {
            return low;
        }
    }

Thanks.

Upvotes: 0

Views: 182

Answers (3)

Paul McJones
Paul McJones

Reputation: 1

Take a look at lower_bound and upper_bound in the C++ Standard Template Library. Those links are to the specifications; the implementations are in the file stl_algo.h in the implementation section of the same web site but I'm a new user and thus not allowed to post more than two URLs at a time.

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234857

Arrays.binarySearch() returns -(insertion_point + 1). That way, return values ≥ 0 are hits and return values < 0 are misses, with insertion_point = -return_value - 1.

Upvotes: 4

user207421
user207421

Reputation: 311048

Take a look at how java.util.Arrays.binarySearch() does it.

Upvotes: 2

Related Questions