二进制搜索终止条件

Question

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

虽然两者都有效但有人能告诉我一个人的实际优势是什么？

Answer 1

In addition to what @templatetypedef said, it is also important to mention that when bounds are inclusive terminating condition should only be low <= high, if terminating condition is kept low < high it will cause 1 element skipped in search. Also when bounds are exclusive terminating condition should only be low < high, if condition is low <= high, it will cause index out of bounds.

I will try to explain it with an example here:

Suppose array is [4, 5, 6] ans we want to search for element 6. Length of array here is 3.

Initialization: We set low = 0. We can either set high = 2 or high = 3. (i.e. Length -1 or Length)

Running loop with high initialized with Length - 1

low = 0, high = 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使用 Length 初始化的运行循环

低 = 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.

请注意，条件不能低 <= 高，因为如果数组中不存在 x，它将导致循环在第二次迭代中运行低 = 3 和高 = 3，这将导致循环第三次运行时索引越界。

Answer 2

您列出的两个终止条件通常根据低端和高端是包含端还是排除端来使用。如果边界是包容性的，则当low = high时，数组中还有一个要检查的元素，并且内部循环应再运行一次。因此，测试低≤高是否合适。另一方面，如果低是包含性的，而高是排他性的，那么当低=高时，您已经用尽了所有元素并完成了操作，因此以低<高的形式进行测试更为合适。