algorithm - 二分查找终止条件

Question

每当我迭代地执行二进制搜索时，我总是对是否应该使用 while (low < high) 感到困惑。或 while(low <= high) .

虽然两者都可以，但有人能告诉我其中一个相对于另一个的实际优势是什么吗？

Answer 1

除了@templatetypedef 所说的之外，还有一点很重要，即当边界是包含 时，终止条件只能是low <= high。 ，如果终止条件保持 low < high 它将导致在搜索中跳过 1 个元素。此外，当边界是排他性时，终止条件应该仅为 low < high ，如果条件为low <= high，会导致索引越界。

我会在这里用一个例子来解释它:

假设数组是 [4, 5, 6] 并且我们要搜索元素 6。这里的数组长度是 3。

初始化:我们设置 low = 0。我们可以设置 high = 2 或 high = 3。(即 Length -1 或 Length)

运行循环 high用长度初始化 - 1

低 = 0，高 = 2

In first iteration
    low = 0, high = 2 and middle = 1.
    array[middle] is 5, so low = middle + 1 i.e. 2

在 if(low < high) 循环的第二次迭代中将终止而不搜索位置 2 处的元素，因此它应该是 if(low <= high)

 In second iteration with if (low <= high) 
    low = 2, high = 2, middle = 2, array[middle] == x, so we return 2.

运行循环 high用长度初始化

低 = 0，高 = 3

In first iteration
    low = 0, high = 3 and middle = 1.
    array[middle] is 5, so low = middle + 1 i.e. 2

In second iteration with if(low < high)
    low = 2, high = 3, middle = 2. array[middle] == x, we return 2.

注意 条件不能是 low <= high 因为如果数组中不存在 x 它将导致循环在第二次迭代中运行 low = 3 和 high = 3 并且这将导致索引输出循环第三次运行时的界限。