Java：二进制搜索

Question

二分搜索算法的实现是否可行？它有效，但它是我想出的实现，与我的导师不同。谁能帮我打个洞？

package algorithm.linearsearch;

public class 二进制搜索 {

public static void main(String[] args) {
    System.out.println(binarySearch(
            new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 26, 109, 1001, 1100 },
            26));

}

private static int binarySearch(int[] array, int target) {
    int p = 0;
    int r = array.length - 1;
    int q;

    while (p <= r) {
        q = (p + r) / 2;
        if (array[q] == target) {
            System.out.println("value: " + array[q]);
            return q;
        }
        if (array[q] > target) {
            r = q + 1;
        } else {
            p = q - 1;
        }

    }

    return -1;

}

}

Answer 1

就是这个

if (array[q] > target) {
    r = q + 1;
} else {
    p = q - 1;
}

应该是

if (array[q] > target) {
    r = q - 1; // index lower to current pivot
} else {
    p = q + 1; // index upper to current pivot
}

Answer 2

有一件事我可以说。如果找到，您的程序应该 return 索引，如果找不到，则应 return -1。因此，您不需要打印值作为从用户那里获取的关于要查找哪个元素的输入。

你需要先检查你的数组是否为空 return -1 以避免在计算数组长度时发生空指针异常。

Java：二进制搜索

Java: Binary Search

java

binary-search