使用开始<的二进制搜索结束与使用开始< =结束 [英] Binary Search using start < end vs. using start <= end

问题描述

在二进制搜索中，我们通常具有低变量和高变量，并且通常有一个while循环，用于测试低< =高，如以下代码所示(来自Wikipedia):

In binary search, we usually have low and high variables and typically there is a while loop that tests if low <= high, as shown in this code (from Wikipedia):

int SortedArray[max] = {....}

int BinarySearch (int key)
{
    int start = 0;
    int end = max - 1;
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (key == a[mid])
            return mid;
        else if (key < a[mid])
            end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

学习二进制搜索时，总是教我start< = end方法，但是当看到其他实现时，我看到很多人都在while(start< end)做.

When learning binary search, I was always taught the start <= end approach, but when seeing other implementations, I've seen a lot of people do while(start < end).

一个相对于另一个有优势吗?在我自己的本机实现中，我使用< =方法，但是当我将其切换为<时，搜索将失败.

Is there an advantage to one versus the other? In my own native implementations, I do the <= approach but when I switch it out for <, the search fails.

使用一个相对于另一个使用是否有经验法则?

Is there a rule of thumb for using one versus the other?

推荐答案

即使您的问题可能不是很清楚，我也可以推断您正在谈论这种二进制搜索的实现(此处为C，来自维基百科) :

even if your question is probably not super clear, I could infer you are talking about this kind of implementation of the binary search (here in C, from Wikipedia):

int SortedArray[max] = {....}

int BinarySearch (int key)
{
    int start = 0;
    int end = max - 1;
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (key == a[mid])
            return mid;
        else if (key < a[mid])
            end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

如果将start <= end替换为start < end，在某些情况下您的算法将无法给出正确的答案.

If you replace start <= end by start < end, there will be cases where your algorithm will not give the good answer.

让我们考虑两个案例.

Let's think about two cases.

1-您想在列表[1]中搜索1.在这种情况下，如果更改循环条件，start = 0, end = 0和算法将返回-1.

1 - You would like to search 1 in the list [1]. In that case, start = 0, end = 0 and the algorithm would return -1 if you change the loop condition.

2-您想在列表[1, 2]中搜索2.在这种情况下，开始= 0，结束=1.算法将在C中设置mid = (0+1)/2=0.因此，arr[mid] < key.它将生成start = 1, end = 1.同样，如果您在此处停止循环，该算法将返回-1而不是1.

2 - You would like to search 2 in the list [1, 2]. In that case, start = 0, end = 1. The algorithm will set mid = (0+1)/2=0 in C. Thus arr[mid] < key. It will make start = 1, end = 1. Again, if you stop the loop here, the algorithm will return -1 instead of 1.

可能还有许多其他示例.

And there are probably many other examples.

祝你有美好的一天

这篇关于使用开始&lt;的二进制搜索结束与使用开始&lt; =结束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！