如果在 JAVA 中的二进制搜索中找不到数字，我如何 return 索引它应该去哪里

Question

所以我有一个二进制搜索代码，可以找到应该放置数字的位置以保持排序顺序。到目前为止，我已经花了一个半小时多一点的时间来尝试解决这个问题，这样我就可以继续推进了。

如果在数组中找不到该值，但找到了应该放置的位置，我会在方法末尾 return 取什么值？基本上一个值表示该数字所属的索引在中间值的 +/- 1 范围内。

这是二进制搜索，我不想更改它，而只是在 _____ 所在的位置寻找 return 的变量。

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

Answer 1

实际代码是return -1。但我对你的描述感到困惑。 "if the value is not found in the array, but the place it should be placed is found?" 是什么意思？该值是否在数组中找到。在while之前没有找到，这意味着它不在数组中，所以你应该return -1.

Answer 2

参见Arrays.binarySearch。

return -low - 1;

一个负数，最多-1。由于 mid（插入点）的范围为 0.

returns

index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Answer 3

大多数方法 return 对放置元素的索引的按位求反，因此 ~idx.

二进制搜索假设 lo 之前的所有元素都小于 key 和 hi 的类似物。

在 hi < lo 的情况下，这意味着 hi 被设置为 mid-1 而 mid 等于 lo （因为 hi和 lo 最多相差一个）或类似于 lo。因此必须放置元素的位置是 lo。因此 returns:

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 为负数的情况下用作插入索引）。

online JDoodle demo.

如果在 JAVA 中的二进制搜索中找不到数字，我如何 return 索引它应该去哪里

How do I return an index of where a number should go if it isn't found in a Binary Search in JAVA

java

arrays

binary-search