How to use recursion when creating a binary search algorithm

Question

I use my free time from the university to practice Java through coding algorithms. One of the algorithms that I encoded was a 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 write a much cleaner and more efficient binary search algorithm, alternative to what I encoded. I saw examples of how recursion is used, for example, when using factorial with numbers that I understand. However, when coding for something of such complexity, I am confused about how to use it to your advantage. So my question is how to apply recursion when coding a binary search algorithm. And if you have any advice for me to improve my recursion skills, even if it should be something that does not take binary search into account, then please feel free to post messages.

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 to do a 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

The following is sample code 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 test cases below against the aforementioned binary search implementation, as well as in the link.

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

Answer 4

Here is the algorithm that should catch you. Let your method signature:

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

• Check if your begin_index> end_index if YES, then return false .
• Calculate mid_element for your input array.
• Check if your search_element this mid_element . if YES returns true
• If mid_element > search_element Call your method with range 0 - mid
• If mid_element < search_element Call your method with a range of mid+1 - Length_of_Array

Just as @DwB said in his comment, you better use a loop to get things done. Some problems are recursive (like binary tree problems). But this is not one of them.

Answer 5

This is another way to do 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; } } } } 

Answer 6

Possible example:

 // 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 out C Binary Search, With and Without Recursion

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

Answer 7

Until it returns an index, it at least returns the idea of ​​yes or no, something 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; } 

Answer 8

BinarySearch recursion with interrupt conditions in case you cannot find the value you are looking for

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

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