如何使用递归创建二进制搜索算法
如何使用递归创建二进制搜索算法
提问于 2013-09-25 18:39:35
我一直在利用我大学之外的时间通过编码算法来练习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;
}
}
}
}我真的想要写一个更干净、更高效的二进制搜索算法，这是我编码的另一种方法。我已经看到了如何使用递归的例子，例如，当使用我理解的数字进行阶乘时。然而，在编写如此复杂的代码时，我很困惑如何使用它来实现我的优势。因此，我的问题是如何在编码二进制搜索算法时应用递归。如果你有任何技巧让我完善我的递归技巧，即使它必须是不考虑二进制搜索，那么请随时张贴。
回答 7
Stack Overflow用户
回答已采纳
发布于 2013-09-25 18:52:50
如果您真的想使用递归，这应该可以做到。
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);
}
}Stack Overflow用户
发布于 2013-09-25 18:52:44
下面是一种更简单的二进制搜索方法：
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
}Stack Overflow用户
发布于 2013-11-03 09:16:25
下面是从这里提取的代码示例。
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()页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19012677
复制相关文章
相似问题
腾讯云开发者
