recursion - 递归二进制搜索方法中的错误?
问题描述
我正在尝试编写一种方法来对一组人员执行二进制搜索。该方法应返回找到此人的索引,如果不存在则返回 -1。出于某种原因,即使该人在数组中,该方法似乎也会返回 -1。请帮助我是初学者。
public static int binarySearchRecursive(Person[] a, Person p) {
int right = a.length -1;
int left = 0;
return binarySearchRecursive(a, p, left, right);
}
private static int binarySearchRecursive(Person[] a, Person p, int left, int right) {
int mid = (left + right) / 2;
if (a[mid].compareTo(p) == 0)
return mid;
if (left == right)
return -1;
else {
if (a[mid].compareTo(p) > 0) {
return binarySearchRecursive(a, p, left, mid);
}
else {
return binarySearchRecursive(a, p, mid, left);
}
}
}
public static void main(String[] args) {
Person s = new Person("shlomo",13);
Person m = new Person("menachem",15);
Person y = new Person("yehuda",18);
Person a = new Person("atara",20);
Person [] array = {s, m, y, a};
解决方案
我可以看到两个问题:
- 在第二个递归调用中,您传递
mid
的是左边界和left
右边界。这似乎不对。 - 如果你搜索最后一个
Person
,never 的计算会mid
前进,并且left
never equalsright
,所以它会无限递归。
推荐阅读
- java - Android:9 补丁启动画面不会保持纵横比
- selenium-webdriver - java升级后Webdriver无法启动测试“无法创建新服务:ChromeDriverService”
- python-3.x - Mac OS Python 3.6 无法 pip 安装任何包(TLS/SSL 证书)
- c# - 通过 id 而不是名称从谷歌云获取对象
- android - 从房间返回接口的 LiveData?
- ssl - 如何在服务器上签署 ssl
- python - 延长 google Oauth2 的 access_token 的寿命
- javascript - setTimeout 和获取请求
- javascript - 如何摆脱代码中的解析错误
- render - 渲染到纹理