如何在创建二进制搜索算法时使用递归

我一直利用大学时间通过编码算法练习Java。 我编码的算法之一是二进制搜索：

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

我真的希望能够编写一个更清晰，更有效的二进制搜索算法，这是我编码的替代方法。 我已经看到了如何使用递归的示例，例如在使用我理解的数字进行阶乘时。 然而，当编写这种复杂性的东西时，我很困惑如何使用它对我有利。 因此我的问题是如何在编码二进制搜索算法时应用递归。 如果你有任何提示让我完善我的递归技巧，即使它必须是不考虑二元搜索的东西，那么请随时发布。

Answer 1

如果你真的想使用递归，这应该这样做。

 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 

Answer 2

这是一种更简单的二分查找方式：

 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

以下是从此处提取的代码示例。

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

您可以在参考链接中找到针对上述二进制搜索实现的以下测试用例的实现。

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

Answer 4

这是一个应该让你前进的算法。 让你的方法签名是：

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

1. 检查你的begin_index> end_index是否为YES然后返回false 。
2. 计算输入数组的mid_element 。
3. 检查您的search_element是否等于此mid_element 。 如果是，则返回true
4. 如果mid_element > search_element使用range 0 - mid调用您的方法
5. 如果mid_element < search_element使用范围mid+1 - Length_of_Array调用您的方法

另外正如@DwB在评论中所说，你最好使用循环来完成任务。 有些问题本质上是递归的（就像二叉树问题一样）。 但这个不是其中之一。

Answer 5

这是另一种递归方式：

 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

一个可能的例子是：

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

在这里，您可以检查C二进制搜索，有和没有递归

资料来源： http ： //www.cs.utsa.edu/~wagner/CS3343/recursion/binsearch.html

Answer 7

虽然它不返回索引，但这至少会返回集合中存在的“是”或“否”的概念：

 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，以防您无法找到所需的值

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

实施

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