Consider the following recursive method:

    /**
     * Searches for a value in a sorted list. Returns true if
     * val is contained in the list t, and false otherwise.
     * 
     * @pre. t.size() is zero or more 
     * @pre. t is in sorted order 
     * @pre. t has no duplicate elements
     * 
     * @param val
     *            a value to search for
     * @param t
     *            a list
     * @return true if val is contained in t, and false otherwise
     */
    public static boolean bsearch(Integer val, List<Integer> t) {
        if (t.size() == 0) {                                       // a
            return false;                                          // b
        }
        int i = t.size() / 2;                                      // c
        Integer mid = t.get(i);                                    // d
        if (val.equals(mid)) {                                     // e
            return true;                                           // f
        } else if (val.compareTo(mid) < 0) {                       // g
            return bsearch(val, t.subList(0, i));                  // h
        } else {                                                   // i
            return bsearch(val, t.subList(i + 1, t.size()));       // j
        }
    }

Prove that the method bsearch is correct using the approach from the lectures (i.e., prove that the base cases are correct and that the recursive case of the method is correct).

First prove the correctness of the base case(s).

Base case 1: A list of size zero contains no values; the base case returns false which is correct.

Base case 2: If the size of the list is greater than zero, then the index i is computed as t.size() / 2, which is guaranteed to lie in the range 0-(t.size() - 1) for any non-zero sized list; therefore, i is a valid index. If val is found in the list at index i, true is returned, which is correct.

Next assume that the recursive invocations are correct and prove under that assumption that the recursive case is correct as well.

Recursive case 1: Assume that bsearch(val, t.subList(0, i)) returns true if val is contained in the part of the list before the element at index i, and false otherwise. The first recursive case runs when val is strictly less than the element at index i. Because the list is sorted, the element must be in the part of the list before the element at index i; therefore, the first recursive case is correct.

Recursive case 2: Assume that bsearch(val, t.subList(i + 1, t.size()) returns true if val is contained in the part of the list after the element at index i, and false otherwise. The maximum value of (i + 1) is equal to t.size() which is a valid index for sublist. The second recursive case runs when val is strictly greater than the element at index i. Because the list is sorted, the element must be in the part of the list after the element at index i; therefore, the second recursive case is correct.

Prove that the method bsearch (from part A) terminates using the approach from the lectures.

First define the size of the problem.

Size of bsearch(val, t): Define the size to be n = t.size(). The size of a list is an integer greater than or equal to zero; therefore, n is a natural number.

Next prove each recursive invocation has a smaller size than the original invocation.

Recursive case 1: The size of bsearch(val, t.subList(0, i))) is equal to the size of the list t.subList(0, i). The size of the list is equal to i = (t.size() / 2) = (n / 2) which is less than n except when n = 0; however, n = 0 is a base case.

Recursive case 2: The size of bsearch(val, t.subList(i + 1, t.size())) is equal to the size of the list t.subList(i + 1, t.size()). The size of the list is equal to (t.size() - (i + 1)) = (n - n / 2 - 1) which is less than n except when n = 0; however, n = 0 is a base case.

In both recursive cases, the size of the recursive invocation is less than n; therefore, the method terminates.