How to use recursion in creating a binary search algorithm

Question

I have been using my time off university to practice Java through coding algorithms. One of the algorithms I coded was the binary search:

public class BinarySearch {

    private static int list[] = {3, 6, 7, 8, 9, 10};

    public static void main(String[] args) {
        BinarySearch b = new BinarySearch();
        b.binarySearch(list);

    }

    public void binarySearch(int[] args) {
        System.out.println("Binary search.");

        int upperBound = args.length;
        int lowerBound = 1;
        int midpoint = (upperBound + lowerBound) / 2;
        int difference = upperBound - lowerBound;

        int search = 7;

        for (int i = 0; i < args.length; i++) {
            if (search < args[midpoint - 1] && difference != 1) {
                upperBound = midpoint - 1;
                midpoint = upperBound / 2;
            } else if (search > args[midpoint - 1] && difference != 1) {
                lowerBound = midpoint + 1;
                midpoint = (lowerBound + upperBound) / 2;

            } else if (search == args[midpoint - 1]) {
                midpoint = midpoint - 1;

                System.out.println("We found " + search + " at position " + midpoint + " in the list.");
                i = args.length;
            } else {
                System.out.println("We couldn't find " + search + " in the list.");
                i = args.length;
            }
        }
    }
}

I really want to be able to write a much cleaner and efficient binary search algorithm, an alternative to what I've coded. I have seen examples of how recursion is used such as when doing factorial with numbers which I understand. However when coding something of this complexity I am confused on how to use it to my advantage. Therefore my question is how do I apply recursion when coding a binary search algorithm. And if you have any tips for me to perfect my recursion skills even if it has to be something that doesn't regard to binary search then please feel free to post.

Answer 1

If you really want to use recursion, this should do it.

public static int binarySearch(int[] a, int target) {
    return binarySearch(a, 0, a.length-1, target);
}

public static int binarySearch(int[] a, int start, int end, int target) {
    int middle = (start + end) / 2;
    if(end < start) {
        return -1;
    } 

    if(target==a[middle]) {
        return middle;
    } else if(target<a[middle]) {
        return binarySearch(a, start, middle - 1, target);
    } else {
        return binarySearch(a, middle + 1, end, target);
    }
}

Answer 2

Here is an easier way of doing binary search:

public static int binarySearch(int intToSearch, int[] sortedArray) {

    int lower = 0;
    int upper = sortedArray.length - 1;

    while (lower <= upper) {

        int mid = lower + (upper - lower) / 2;

        if(intToSearch < sortedArray[mid]) 

            upper = mid - 1;

        else if (intToSearch > sortedArray[mid]) 

            lower = mid + 1;

        else 

            return mid;
    }

    return -1; // Returns -1 if no match is found
}

Answer 3

Following is a code sample extracted from here.

public class BinarySearch {

    public boolean find(int[] sortedValues, int value) {
        return search(sortedValues, value, 0, sortedValues.length - 1);
    }

    private boolean search(int[] sorted, int value, int leftIndex, int rightIndex) {

        // 1. index check
        if (leftIndex > rightIndex) {
            return false;
        }

        // 2. middle index
        int middle = (rightIndex + leftIndex) / 2;

        // 3. recursive invoke
        if (sorted[middle] > value) {
            return search(sorted, value, leftIndex, middle - 1);
        } else if (sorted[middle] < value) {
            return search(sorted, value, middle + 1, rightIndex);
        } else {
            return true;
        }
    }
}

You can find implementations of the below test cases against the above binary search implementation as well in the reference link.

1. shouldReturnFalseIfArrayIsEmpty()
2. shouldReturnFalseIfNotFoundInSortedOddArray()
3. shouldReturnFalseIfNotFoundInSortedEvenArray()
4. shouldReturnTrueIfFoundAsFirstInSortedArray()
5. shouldReturnTrueIfFoundAtEndInSortedArray()
6. shouldReturnTrueIfFoundInMiddleInSortedArray()
7. shouldReturnTrueIfFoundAnywhereInSortedArray()
8. shouldReturnFalseIfNotFoundInSortedArray()