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

本文介绍了如何在创建二进制搜索算法时使用递归的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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

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.

推荐答案

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

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