插值搜索中循环后‘if key == arr[low]: return low’语句的作用是什么？

我看到部分Python实现的插值搜索算法，会在while循环结束后加入这段代码：

if key == arr[low]:
    return low

完整的实现代码如下：

def interpolation_search(arr, key):
    low = 0
    high = len(arr) - 1

    while arr[high] != arr[low] and arr[low] <= key <= arr[high]:
        mid = low + ((key - arr[low]) * (high - low) // (arr[high] - arr[low]))

        if key == arr[mid]:
            return mid
        elif key < arr[mid]:
            high = mid - 1
        else:
            low = mid + 1

    if key == arr[low]:
        return low

    return -1

我已经针对多种列表（均匀分布、非均匀分布、带少量重复的有序数组等）做了大量测试，遍历每个元素搜索，但有无这段语句并未产生结果差异。想知道这段语句的实际作用是什么？

解答 #

这段语句是用来处理搜索区间内所有元素都相同，或者循环结束后区间缩小到单个元素且该元素就是目标值的极端场景：

1. 先看while循环的退出条件：当arr[high] == arr[low]，或者key不在[arr[low], arr[high]]范围内时，循环终止。
2. 如果是arr[high] == arr[low]的情况，意味着当前搜索区间里的元素全部相同（或者只剩一个元素），此时循环内部的逻辑根本不会执行。如果这个相同的元素正好是目标key，没有这段语句的话，函数会直接返回-1，出现错误；而这段语句就能检查这个元素并返回正确的索引。

举个典型测试用例：数组arr = [7,7,7,7]，搜索key=7。此时初始low=0，high=3，因为arr[high] == arr[low]，循环直接跳过。如果没有这段语句，函数会返回-1，但实际上目标元素存在；加上这段语句就能正确返回0。

你之前测试没发现差异，大概率是没覆盖到这种全元素相同的极端场景，或者测试的重复元素在循环过程中已经被mid命中并返回了。

内容的提问来源于stack exchange，提问作者socialtonics