c++ - 高效的二分搜索

Question

在二分搜索的两种不同实现中，哪一种更有效，为什么？

一般来说，二分搜索将一个已排序的数组一分为二，用运算符 < 或 > 将目标条目与数组的两个分割部分进行比较，并不断迭代直到完成或找到目标条目。

int a[8] = {1, 3, 4, 5, 7, 8, 9, 11};

1.

while ( size > 1)
{
    mid = low + (size/2);
    if (a[mid] > find)
    {
       size = mid - low;
    }
    else
    {
        size = size - (mid - low);
        low = mid;
    }
}

2.

while (low <= size)
{
    mid = (low + size)/2;
    if (a[mid] < find)
    {
        low = mid + 1;
    }
    else if (a[mid] > find)
    {
        size = mid - 1;
    }
    else
    {
        break;
    } 
}

在搜索 6 时，第一个，迭代为，

mid = 4 size = 4 low = 0
mid = 2 size = 2 low = 2
mid = 3 size = 1 low = 3
5

而第二个则进行更多迭代并获取下一个条目。

mid = 4 size = 3 low = 0
mid = 1 size = 3 low = 2
mid = 2 size = 3 low = 3
mid = 3 size = 3 low = 4
7

哪一个是高效的？

标签： c++binary-search