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.

Japonica

binary search is simple to write using a loop. using recursion is unnecessary. – Decrepitude

If you must use recursion, which I try to avoid because I see it as terrible (note that this is an opinion), the do not pass the array, instead pass the array, a left index and a right index; the indices identify the boundary of the search. – Decrepitude

@Decrepitude Ah okay, though would there be any advantages of using recursion with binary search does it simplify the algorithm more? – Japonica

This method would be more useful if it returned the index, instead of printing it – Tirade

@Decrepitude Okay I'm slightly confused you said to not pass the array then to instead pass the array and do you mean like list[n...list.length]? In this case n being an integer which is a particular index within the array? – Japonica

@Tirade True say, I might actually do that now. Though for some odd reason when I make a method which returns something it tends to not show it on the terminal in netbeans. So I basically am forced to use a print statement above the return statement to test it. – Japonica

dont pass a partial array, just send the entire array with the left and right bounds. like the cruncher answer. – Decrepitude

Rather than have the method print it, you can call the method and print the result. System.out.println(binarySearch(args)); – Tirade

@Japonica My answer shows how to pass the bounds, rather than actually a smaller array. – Tirade

As others have said, recursion is a poor choice when a loop will do the job as simply or nearly so. – Tiro

@Tirade Oh wow I didn't see that one now totally missed it haha. Yep that's a way of doing it. – Japonica

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

Tirade

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. – Japonica

@Japonica 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 – Tirade

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

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

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

@Discontinuity 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.. – Tirade

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? – Ashleyashli

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

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

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
}

Comer

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 – Japonica

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

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. – Japonica

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

Ulterior

Answer 4

A possible example is :

// need extra "helper" method, feed in params
   public int binarySearch(int[] a, int x) { 
      return binarySearch(a, x, 0, a.length - 1);
   }

   // need extra low and high parameters
   private int binarySearch(int[ ] a, int x,
         int low, int high) {
      if (low > high) return -1; 
      int mid = (low + high)/2;
      if (a[mid] == x) return mid;
      else if (a[mid] < x)
         return binarySearch(a, x, mid+1, high);
      else // last possibility: a[mid] > x
         return binarySearch(a, x, low, mid-1);
   }

Here you can check in C Binary Search, With and Without Recursion

Source : http://www.cs.utsa.edu/~wagner/CS3343/recursion/binsearch.html

Avertin

Answer 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.

Darreldarrell

Answer 6

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

Cerda

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. – Skelp

Answer 7

While it doesn't return the index, this at least returns the idea of 'yes' or 'no' that something is in the collection:

public static boolean recursive(int[] input, int valueToFind) {
    if (input.length == 0) {
        return false;
    }

    int mid = input.length / 2;
    if (input[mid] == valueToFind) {
        return true;
    } else if (input[mid] > valueToFind) {
        int[] smallerInput = Arrays.copyOfRange(input, 0, mid);
        return recursive(smallerInput, valueToFind);
    } else if (input[mid] < valueToFind) {
        int[] smallerInput = Arrays.copyOfRange(input, mid+1, input.length);
        return recursive(smallerInput, valueToFind);
    }

    return false;
}

Cuffs

Answer 8

A recursion BinarySearch with break conditions in case you can not find the value you are looking for

public interface Searcher{
    public int search(int [] data, int target, int low, int high);
}

The Implementation

public class BinarySearch implements Searcher {

    public int search(int[] data, int target, int low, int high) {
        //The return variable
        int retorno = -1;
        if(low > high) return retorno;
        int middle = (high + low)/2;
        if(target == data[middle]){
            retorno = data[middle];
        }else if(target < data[middle] && (middle - 1 != high)){
            //the (middle - 1 != high) avoids beeing locked inside a never ending recursion loop
            retorno = search(data, target, low, middle - 1);
        }else if(target > data[middle] && (middle - 1 != low)){
            //the (middle - 1 != low) avoids beeing locked inside a never ending recursion loop
            retorno = search(data, target, middle - 1, high);
        }else if(middle - 1 == low || middle - 1 == high){
            //Break condition if you can not find the desired balue
            retorno =  -1;
        }
        return retorno;
    }
}

Waves