algorithm - 这个二分查找算法会不会陷入死循环？

Question

具体的二分查找实现如下图。我想问的问题是算法有没有可能死循环？

我能想到的一种可能情况是 l == r == UINT_MAX 并且目标 x 大于数组中的所有元素。难道在这种情况下算法会陷入死循环？

还有没有其他情况会陷入死循环？

感谢您的帮助!!!

// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1.
int binarySearch(vector<double> arr, double x) {
    unsigned int l = 0;
    unsigned int r = arr.size() - 1;
    while (l <= r) {
      int m = l + (r - l) / 2;
      if (arr[m] == x) 
          return m;  
      if (arr[m] < x) 
          l = m + 1; 
      else
          r = m - 1; 
    }
    return -1; 
}

Answer 1

不，它没有!如果 l 和 r 可能永远保持在相同的值，那么这里只会发生无限循环。为此，需要发生以下情况之一:

1) l 的新值 = l 的旧值:

m + 1 = l + (r - l)/2 + 1 = l --> (r - l)/2 + 1 = 0(这永远不会发生，因为左边是总是肯定知道 r 已经大于 l)

2) r 的新值 = r 的旧值:

m - 1 = l + (r - l)/2 - 1 = r --> (r - l)/2 = r - l + 1(这也永远不会发生，因为右边总是更大)