arrays - 下面代码中函数内部的 (if block) 的作用是什么？

Question

这是我在 YouTube 视频中找到的插值搜索，但没有声音。我已经理解了代码中的大部分内容，但为什么我需要使用 if(key == arr[low])？

if (key == arr[low]){

    return low ;

} else {

    return -1;

}

整个程序在下面。

#include <iostream>
#include <cmath>
using namespace std;

int z = 0;

int interpolation(int arr[], int left, int right, int key){

    int low = left;
    int high = right - 1;
    int mid;

    while (arr[high] != arr[low] && key >= arr[low] && key <= arr[high]) {

        mid = low + ( (key - arr[low]) * (high - low) / (arr[high] - arr[low]) );

        if (key > arr[mid]){

            low = mid + 1;

        } else if (key < arr[mid]){

            high = mid - 1;

        } else{

            return mid;

        }

    }

    if (key == arr[low]){

        return low ;

    } else {

        return -1;

    }

}

int main()
{

    int L[] = {0, 1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
    //int L[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int left = 0;
    int right = sizeof(L) / sizeof(L[0]);

    int key = 6;

    int x;
    if((x = interpolation(L, left, right, key)) == -1 ){

        cout << "Key doesn't exist"<< endl;

    } else {

        cout << "The position of Key is " << x << endl;

    }

return 0; }

如果没有这部分，一些索引就无法工作。但是，while 循环中的 else 不是涵盖了整个事情吗？

else{

     return mid;

}

谢谢。

Answer 1

当 while循环结束，以下一个或多个条件为真:

1. arr[high] == arr[low] , 或
2. key < arr[low] , 或
3. key > arr[high]

这是 DeMorgan's Laws 的应用程序至 while的延续条件。

如果只有条件 2 或 3 为真，key没有找到，所以算法返回 -1 .如果条件 1 为真，您会发现 high 之间有一段“平坦”的延伸和 low .在这种情况下，算法应返回 low 之间的任何索引。和 high如果arr[low]或 arr[high]匹配key ;如果平面拉伸(stretch)中的数字与 key 不匹配, 返回-1。

isn't the else inside the while loop covering the whole thing?

如果您在使用搜索键找到该点之前发现了平坦的拉伸(stretch)，您可能无法到达循环中的那个部分。你需要这个条件，因为当函数运行平坦时梯度搜索是不可能的。