二进制搜索程序不能打印正确的索引
二进制搜索程序不能打印正确的索引
提问于 2021-10-30 18:09:22
我需要创建一个二进制搜索程序，如果搜索键在数组中，它返回ai等于key的最大索引i，否则返回-i，其中i是最大的索引，使得ai小于key。
示例运行如下所示。
更多input.txt 2 3 4 5 6 6 6 7 8 9 11
java BinarySearch input.txt 10
-9
java BinarySearch input.txt 6
6
到目前为止，程序将为输入文件中的数字打印正确的索引，但当我输入一个不在列表中的数字时，它不会打印-i。例如，当我在命令行中输入10时，它不会打印-9；相反，它会打印-10。
public class BinarySearch{
public static int search(int key, int [] a, int lo, int hi)
{
int n = a.length;
if (hi >= lo)
{
int mid = lo + (hi - lo) / 2;
if ((mid == n-1 || key < a[mid+1]) && a[mid] == key)
return mid;
else if (key < a[mid])
return search(key, a, lo, (mid-1));
else return search(key, a, (mid+1), hi);
}
return -1*lo;
}
public static void main (String [] args)
{
In in = new In(args[0]);
int key = Integer.parseInt(args[1]);
int [] a = in.readAllInts();
System.out.println(search(key, a, 0, a.length-1));
}
}回答 1
Stack Overflow用户
发布于 2021-10-31 06:45:11
public static int search(int key, int [] a, int lo, int hi)
{
int n = a.length;
if (hi > lo)
{
int mid = lo + (hi - lo) / 2;
if ((mid == n-1 || key < a[mid+1]) && a[mid] == key)
return mid;
else if (key < a[mid])
return search(key, a, lo, (mid-1));
else return search(key, a, (mid+1), hi);
} else if(hi == lo && n == hi) {
return -1*(lo);
} else if(lo > hi) {
return -1;
}
return -1*(lo-1);
}我添加了两个条件：
当hi==lo && hi == n表示数组的最大值小于key且search()返回最高索引时的
- -(I)当
lo > hi表示数组的最小值大于key且-1\f25search()-1\f6返回-1\f25
-1\f6<-1\f25 G210-1\f6
并编辑了当lo == hi和hi != n返回前一个索引(i)时在return -1*(lo-1);之前不满足的所有其他条件
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69780890
复制相关文章
相似问题
腾讯云开发者
