二分查找条件

Question

二分查找条件

7

我经常对二分搜索算法的条件感到困惑，在编程竞赛中浪费了很多时间。我的问题是什么时候使用以下每个条件？
1. while (low < high)
2. while (high - low > 1)
3. while (low <= high)
low = 解集合中的最小值。
high = 解集合中的最大值。

- Omar Abdelrahman

4

你能告诉我们你对于“低”和“高”的定义是什么吗？ - nanofarad

没有更多的代码/信息，这个问题无法回答。 - deviantfan

2

像任何递归过程一样，您需要仔细考虑基本情况。这必须是一个始终会被触发的情况，并且您已经准备好在没有进一步递归的情况下处理它。 - Patricia Shanahan

@deviantfan 这正是我提出这个问题的原因，因为我不知道在任何二分查找问题中何时使用它们中的每一个，我只是尝试其中的每一个，直到其中一个起作用，没有逻辑原因，只是凭直觉。 - Omar Abdelrahman

http://algs4.cs.princeton.edu/11model/BinarySearch.java.html 可能会给你一些思路。 - user2425429

1

我相信这个问题已经非常清楚地表达了（至少在编辑之后）。为什么它仍然被关闭？ - Appaji Chintimi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Kurlak · Accepted Answer

while (low < high) 用于搜索区间 [low, high)。更新 high 时，使用 high = mid。更新 low 时，使用 low = mid + 1。
while (high - low > 1) 用于搜索区间 (low, high)。更新 high 时，使用 high = mid。更新 low 时，使用 low = mid。
while (low <= high) 用于搜索区间 [low, high]。更新 high 时，使用 high = mid - 1。更新 low 时，使用 low = mid + 1。

以下是代码：

public class BinarySearch {
    public static void main(String[] args) {
        Integer[] nums = { 4, 9, 12, 18, 20, 26, 28, 29, 55 };

        for (int i = 0; i < nums.length; ++i) {
            System.out.println(binarySearch1(nums, nums[i]));
            System.out.println(binarySearch2(nums, nums[i]));
            System.out.println(binarySearch3(nums, nums[i]));
        }
    }

    public static <T extends Comparable<T>> int binarySearch1(T[] array, T value) {
        final int NOT_FOUND = -1;
        int low = 0;
        int high = array.length;

        while (low < high) {
            int mid = low + (high - low) / 2;
            int comparison = array[mid].compareTo(value);

            if (comparison == 0) {
                return mid;
            } else if (comparison > 0) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return NOT_FOUND;
    }

    public static <T extends Comparable<T>> int binarySearch2(T[] array, T value) {
        final int NOT_FOUND = -1;
        int low = -1;
        int high = array.length;

        while (high - low > 1) {
            int mid = low + (high - low) / 2;
            int comparison = array[mid].compareTo(value);

            if (comparison == 0) {
                return mid;
            } else if (comparison > 0) {
                high = mid;
            } else {
                low = mid;
            }
        }

        return NOT_FOUND;
    }

    public static <T extends Comparable<T>> int binarySearch3(T[] array, T value) {
        final int NOT_FOUND = -1;
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int comparison = array[mid].compareTo(value);

            if (comparison == 0) {
                return mid;
            } else if (comparison > 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return NOT_FOUND;
    }
}