二进制搜索不起作用。错误的 "first" 和 "last"

Question

public class Programma {

    public static void main(String args[]) {
        int array[] = { 1, 2, 4, 5, 6, 7, 8 };
        int v = 4;
        int first = 0;
        int last = 6;
        if (binary_search(array, v, first, last) == 1) {
            System.out.println("Value " + v + " found!");
        } else {
            System.out.println("Value " + v + " not found.");
        }
    }

    static int binary_search(int array[], int v, int first, int last) {
        if (first > last) {
            return 0;
        }
        int m = (first + last) / 2;
        System.out.println("Actual m is: " + m + " of " + first + last);
        if (array[m] == v) {
            return 1;
        } else if (v > array[m]) {
            binary_search(array, v, m + 1, last);
        } else {
            binary_search(array, v, first, m - 1);
        }
        return -1;
    }
}

输出为：

Actual m is: 3 of 06
Actual m is: 1 of 02
Actual m is: 2 of 22
Value 4 not found.

我真的不明白为什么first和last从06变成02，而它们应该变成46，因为3小于4....我添加了条件 if (v>array[m]) 应该完成工作但实际上没有。

Answer 1

您忘记检索 binary_search 的结果：

if (array[m] == v)
    return 1;
if (v > array[m])
    return binary_search(array, v, m + 1, last);
return binary_search(array, v, first, m - 1);

我认为您可以简化代码和 select 主要 binary_search 方法来接受 array 并要求 value:

public static void main(String... args) {
    int[] arr = { 1, 2, 4, 5, 6, 7, 8 };
    int val = 4;
    int pos = binarySearch(arr, val);

    if (pos == -1)
        System.out.format("Value %s was not found.\n", val);
    else
        System.out.format("Value %d was found at position %d\n", val, pos);
}

public static int binarySearch(int[] arr, int val) {
    return binarySearch(arr, val, 0, arr.length - 1);
}

private static int binarySearch(int[] arr, int val, int left, int right) {
    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == val)
            return mid;
        if (arr[mid] < val)
            left = mid + 1;
        else if (arr[mid] > val)
            right = mid - 1;
    }

    return -1;
}

Answer 2

如果您正在寻找解决方案而不是出于研究目的，您可以使用为其创建的方法。

    import java.util.Arrays;
    public static void main(String[] args) 
    { 
        int intArr[] = {10,20,15,22,35};
        int intKey = 22;
        Arrays.sort(intArr); 
        System.out.println(intKey + " found at index = " + Arrays.binarySearch(intArr,intKey));
    }

二进制搜索不起作用。错误的 "first" 和 "last"

Binary search does not work. Wrong "first" and "last"

java

binary-search