以下のコード内の関数内の（ブロックの場合）の役割は何ですか？

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つ以上が真である：

1. arr[high] == arr[low]、又は
2. key < arr[low]、又は
3. key > arr[high]

これはのアプリケーションでありますDeMorgan's Laws〜whileの継続条件。

条件2または3のみが真である場合、keyは見つからないため、アルゴリズムは-1を返します。条件1が真である場合、highとlowの間に「フラット」ストレッチがあります。この場合、arr[low]またはarr[high]がkeyと一致する場合、アルゴリズムはlowとhighの間の任意のインデックスを返します。フラットストレッチの数値がkeyと一致しない場合は-1を返します。

全体がカバーするwhileループの中にelseはありませんか？

フラットなストレッチが見つかってから検索キーを押すと、その部分に戻ることはできません。この条件が必要なのは、関数がフラットで実行されているときに勾配検索ができないためです。