对于数组中的键的二进制搜索，lo 或 hi 的最终值是多少？

Question

假设整数键与排序键数组：int[] keys = {10,20,30,40,50,60,70}; 所以最初在排名 lo = 0 和 hi = 6.

二分查找keys数组中的30，最后lo的值会不会是20，也就是1？

我只需要弄清楚逻辑。

Answer 1

二进制搜索将像这样开始：

lo = 0, hi = 6, mid = 3, numberInMid = 40

如30 < 40、hi = mid - 1 = 2

现在，
lo = 0, hi = 2, mid = 1, numberInMid = 20

如30 > 20、lo = mid + 1 = 2

最后，
lo = 2, hi = 2, mid = 2, numberInMid = 30

作为30 == 30，循环退出并且ans = 30 相反，如果您搜索的是 35（我取这个数字是因为它符合上述所有关系表达式），那么：
作为 35 > 30、lo = mid + 1 = 3、
由于 lo > hi，循环退出并且您返回默认值 ans。
例如：ans = -1 如果只涉及正整数，或者相反，您甚至可以使用 flag = false，它仅在 == 表达式被命中时才切换为真。

Answer 2

您可以通过debug实现代码并跟踪代码以了解。

public class Test {
    public int binary_search(int[] keys, int low, int high, int mid, int target){
        if(low > high){
            return -1;
        }

        if(target < keys[mid]){
            high = mid - 1;
            mid = (low + high) / 2;
            return binary_search(keys, low, high, mid, target);
        }else if(target > keys[mid]){
            low = mid + 1;
            mid = (low + high) / 2;
            return binary_search(keys, low, high, mid, target);
        }else{
            return mid;
        }
    }

    public static void main(String args[]){
        int[] keys = {10,20,30,40,50,60,70};
        Test test = new Test();
        int mid = (0 + keys.length) / 2;
        int target = 30;
        int index = test.binary_search(keys, 0, keys.length, mid, target); 
        System.out.println(index);
    }
}

对于数组中的键的二进制搜索，lo 或 hi 的最终值是多少？

For binary search for keys in an array, what is the final value of lo or hi?

java

arrays

search

rank