我上大学期间一直在通过编码算法来练习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) { 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; } } } }
我真的希望能够编写一种更简洁,有效的二进制搜索算法,以替代我编写的代码。我已经看到了如何使用递归的示例,例如使用我理解的数字进行阶乘时。但是,当编写这种复杂的代码时,我对如何利用它感到困惑。因此,我的问题是编码二进制搜索算法时如何应用递归。如果您有什么技巧可以完善我的递归技能,即使它不必与二进制搜索无关,也请随时发表。
如果您确实要使用递归,则应该这样做。
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); } }