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.

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

Solution 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
}

Solution 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()

Solution 4

This is another way of doing recursion:

int[] n = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
@Test
public void testRecursiveSolution() {
    Assert.assertEquals(0, recursiveBinarySearch(1,n));
    Assert.assertEquals(15, recursiveBinarySearch(16,n));
    Assert.assertEquals(14, recursiveBinarySearch(15,n));
    Assert.assertEquals(13, recursiveBinarySearch(14,n));
    Assert.assertEquals(12, recursiveBinarySearch(13,n));
    Assert.assertEquals(11, recursiveBinarySearch(12,n));
    Assert.assertEquals(10, recursiveBinarySearch(11,n));
    Assert.assertEquals(9, recursiveBinarySearch(10,n));
    Assert.assertEquals(-1, recursiveBinarySearch(100,n));
}
private int recursiveBinarySearch(int n, int[] array) {
    if(array.length==1) {
        if(array[0]==n) {
            return 0;
        } else {
            return -1;
        }
    } else {
        int mid = (array.length-1)/2;
        if(array[mid]==n) {
            return mid;
        } else if(array[mid]>n) {
            return recursiveBinarySearch(n, Arrays.copyOfRange(array, 0, mid));
        } else {
            int returnIndex = recursiveBinarySearch(n, Arrays.copyOfRange(array, mid+1, array.length));
            if(returnIndex>=0) {
                return returnIndex+mid+1;
            } else {
                return returnIndex;
            }
        }
    }
}

Solution 5

Here is a algorithm which should get you going. Let your method signature be:

public boolean binarysearchRecursion(Array, begin_index,end_index, search_element)

1. Check if your begin_index > end_index if YES then return false.
2. Calculate mid_element for your input array.
3. Check if your search_element is equal to this mid_element. if YES return true
4. If mid_element > search_element Call your method with for range 0 - mid
5. If mid_element < search_element Call your method with for range mid+1 - Length_of_Array

Also as @DwB said in his comment you are better using loop to get things done. Some problems are recursive in nature(Like binary tree problems). But this one is not one of them.

View more solutions

Comments

[JP24]

Ah I guess I went all complicated, but then again Java is my first language and I only done programming in it for just about 9 months mostly picked up the skills during study at university and stamped down on the basics when amatuer through self-study and these algorithms are to increase my development though the experience has really helped and it does make me happy to see it work even though it has a lot going on. :D

[Sajal Dutta]

@JP24 That is why programming is so much fun only if you are having fun with it! :)

[JP24]

Yep it is fun, I hated it to bits the first 3 weeks after that I excelled a lot I managed to have the basics fully understood in a matter of just over a month.

[JP24]

This is a great example for recursion, I basically debugged it and ran through how it works. I just managed to make a recursive bubblesort algorithm from scratch. This example has really helped me to get to know how it works. I tried looking over factorial but it didn't really help me that much because it was just too basic.

[Cruncher]

@JP24 Glad I could help :). It's interesting that you mentioned the factorial example. That was the first example that I saw for recursion about 5 years ago. I dismissed it as interesting at BEST, mainly because of the overly simple example. The first time time I used recursion, I was writing a minesweeper game. Trying to get the loop to cascade the board when you click a square that is touching no bombs, I was having major problems. And I had a sudden epiphany that recursion would make the problem so easy!. Sorry about the rant, just thought I'd share my "aha!" moment

[Vasile Surdu]

what if the array is not sorted? the target < arr[middle] etc won't work here since the elements are unsorted

[Cruncher]

@VasileSurdu if the array is not sorted then you can't do a binary search. The question is about binary search.

[CodeDreamer68]

What if your array contains duplicates and the goal is to determine the first occurrence (having the smallest index value)?

[Cruncher]

@CodeDreamer68 then that would be a more strict requirement. However, you could guarantee that with some post-processing. Just step backwards in the array until the value is different..

[Mr Chasi]

I find this to be the best solution. However, I'm just wondering; if one wanted to make a class full of static search-algorithm methods, would it be good practise to make the second method private, and make only the first one public?

[Cruncher]

@MrChasi Probabaly yes. There's not much reason for the outside world to call the second one

[Brij Raj Kishore]

@Cruncher what is wrong in [this code I have made some changes in yours] (code.geeksforgeeks.org/W42WYB). Thanks

[Amr Mostafa]

I was wondering how to return the right index with a recursive solution that has an array of a single element as the base case. Thanks for posting a different recursive solution.