Question

From Algorithms 4^th Ed by Sedgewick, Robert. Ex 1.4.10(modified)

Exercise 1.4.10

I’m modifying the exercise from what’s in the book. I want two functions, lower_bound() and upper_bound(), defined as:

int lower_bound(int[] a, int key)

int upper_bound(int[] a, int key)

lower_bound() should return the index of the first (lowest indexed) element of a that is greater than or equal to key, and upper_bound() returns the index of the first (lowest indexed) element of a that is greater than key. You may assume the array is sorted – take that as a hint that something like a binary search is needed. If every element of a is less than the key, both upper_bound and lower_bound return the length of a. If every element of a is less than or equal to key, upper_bound returns the length of a.

Here are some examples:

a = { 1, 1, 2, 2, 4, 4, 4, 5, 6, 6 }

lower_bound(a,0) returns 0               upper_bound(a,0) returns 0

lower_bound(a,3) returns 4               upper_bound(a,3) returns 4

lower_bound(a,2) returns 2               upper_bound(a,2) returns 4

lower_bound(a,4) returns 4               upper_bound(a,4) returns 7

lower_bound(a,6) returns 8               upper_bound(a,6) returns 10

lower_bound(a,7) returns 10               upper_bound(a,7) returns 10

Both algorithms must run in log(N) time. This means you cannot simply use the book’s binary search and then increment backward and forward as needed, since that could take time proportional to N in the worst case. (For example, consider looking for a 1 in an array with a million 1s. Binary search would immediately return the middle index, and then lower_bound and upper_bound would each run through a half million elements looking for the first and last matches.)

Answer 1

public class Bounds {

    static int lower_bound(int[] a, int key){
        int left = 0;
        int right = a.length - 1;
        int mid;
        while(left != right){
            if(left == right - 1){
                if(a[left] >= key)
                    return left;
                else if(a[right] >= key)
                    return right;
                else return a.length;
            }
            mid = (left + right) / 2;
            if(a[mid] < key){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if(a[left] >= key)
            return left;
        else
            return a.length;
    }

    static int upper_bound(int[] a, int key){
        int left = 0;
        int right = a.length - 1;
        int mid;
        while(left != right){
            if(left == right - 1){
                if(a[left] > key)
                    return left;
                else if(a[right] > key)
                    return right;
                else return a.length;
            }
            mid = (left + right) / 2;
            if(a[mid] <= key){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if(a[left] > key)
            return left;
        else
            return a.length;
    }

    public static void main(String[] args){
        int[] a = { 1, 1, 2, 2, 4, 4, 4, 5, 6, 6 };
        System.out.println("lower_bound(a, 0): " + lower_bound(a, 0));
        System.out.println("lower_bound(a, 3): " + lower_bound(a, 3));
        System.out.println("lower_bound(a, 2): " + lower_bound(a, 2));
        System.out.println("lower_bound(a, 4): " + lower_bound(a, 4));
        System.out.println("lower_bound(a, 6): " + lower_bound(a, 6));
        System.out.println("lower_bound(a, 7): " + lower_bound(a, 7));


        System.out.println("upper_bound(a, 0): " + upper_bound(a, 0));
        System.out.println("upper_bound(a, 3): " + upper_bound(a, 3));
        System.out.println("upper_bound(a, 2): " + upper_bound(a, 2));
        System.out.println("upper_bound(a, 4): " + upper_bound(a, 4));
        System.out.println("upper_bound(a, 6): " + upper_bound(a, 6));
        System.out.println("upper_bound(a, 7): " + upper_bound(a, 7));
    }

}

$\color{red}\underline{Output:}$

lower_bound(a, 0): 0
lower_bound(a, 3): 4
lower_bound(a, 2): 2
lower_bound(a, 4): 4
lower_bound(a, 6): 8
lower_bound(a, 7): 10
upper_bound(a, 0): 0
upper_bound(a, 3): 4
upper_bound(a, 2): 4
upper_bound(a, 4): 7
upper_bound(a, 6): 10
upper_bound(a, 7): 10