所以我有一个二进制搜索代码,可以找到应该放置数字的位置以保持排序顺序。到目前为止,我已经花了一个半小时多一点的时间来尝试解决这个问题,这样我就可以继续推进了。
如果在数组中找不到值,但找到了应该放置的位置,我在方法结束时会返回什么值?基本上是一个值,表示该数字所属的索引在中间值的 +/- 1 范围内。
这是二分搜索,我不打算更改它,而只是寻找变量以返回 _____ 所在的位置。
private static int bsearch( int[] arr, int count, int key )
{
if (count==0) return -1;
int lo = 0, hi = count - 1, mid;
while(hi >= lo)
{
mid = (lo + hi) / 2;
if(arr[mid] == key) return mid;
if ( key < arr[mid] ) hi = mid-1;
else lo = mid+1;
}
return _____;
}
最佳答案
大多数方法返回放置元素的索引的按位求反,因此 ~idx
.
二分查找假设lo
之前的所有元素小于 key
和模拟 hi
.
万一hi < lo
, 这意味着 hi
被设置为 mid-1
和 mid
等于 lo
(因为 hi
和 lo
最多不同)或类似于 lo
.因此必须放置元素的位置是 lo
。 .因此返回:
return ~lo;
该算法的优化版本是:
private static int bsearch( int[] arr, int count, int key) {
if (count==0) return -1;
int lo = 0, hi = count - 1, mid = hi>>1;
while(hi >= lo) {
mid = (lo + hi) >> 1;
if ( key < arr[mid] ) hi = mid-1;
else if ( key > arr[mid] ) lo = mid+1;
else return mid;
}
return ~lo;
}
作为测试用例:
for(int i = 0; i <= 22; i++) {
int r = bsearch(new int[] {2,3,7,9,11,15,21},7,i);
System.out.println(""+i+" -> "+r+" "+(~r));
}
给出:
0 -> -1 0
1 -> -1 0
2 -> 0 -1
3 -> 1 -2
4 -> -3 2
5 -> -3 2
6 -> -3 2
7 -> 2 -3
8 -> -4 3
9 -> 3 -4
10 -> -5 4
11 -> 4 -5
12 -> -6 5
13 -> -6 5
14 -> -6 5
15 -> 5 -6
16 -> -7 6
17 -> -7 6
18 -> -7 6
19 -> -7 6
20 -> -7 6
21 -> 6 -7
22 -> -8 7
x -> i j
与 i
结果和j
按位负数(在 i
为负数的情况下用作插入索引)。
关于java - 如果在 JAVA 的二进制搜索中找不到数字,如何返回该数字应该去向的索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29284490/