constポインタを使用したバイナリ検索

Question

バイナリ検索を使用して値がkeyであるかどうかをチェックし、trueまたはfalseを指定する関数を実装する必要があります。

bool binary_search(const int* begin, const int * end, int key){ 
    if(begin < end){ 
     int mid = (end-begin)/2; 
     if(mid == key){ 
      return true; 
     }else if (key < mid){ 
      int h = mid-1; 
      end = &h; 
      binary_search(begin, end, key); 
     }else if (mid < key){ 
      int i = mid+1; 
      begin = &i; 
      binary_search(begin, end, key); 
     } 
    }else{ 
     return false; 
    } 
} 

が、それは任意の出力が得られないだろうが、その代わり、それは私にエラーを与える：

私はこのように書きます。

warning: control reaches end of non-void function [-Wreturn-type]

私は本当に私がここでやることが、誰かが間違ってここに何が起こっているかを私に説明することができます持っているものを理解していませんか？

Answer 1

可能なすべてのブランチでreturnを指定する必要があります。

変更

binary_search(begin, end, key); 

return binary_search(begin, end, key); 

に再帰呼び出しから結果を返します。これらの場合はelse文

}else if (key < mid){ 
    int h = mid-1; 
    end = &h; 
    binary_search(begin, end, key); 
}else if (mid < key){ 
    int i = mid+1; 
    begin = &i; 
    binary_search(begin, end, key); 
} 

関数の場合には

Answer 2

は何も返しません。つまり、これらのコードブロックにはreturn文がありません。

例えばこれらの文

int mid = (end-begin)/2; 
if(mid == key){ 

に代えてインデックス中間の配列の要素の値を持つキーを比較する配列のインデックスと比較キーがあるので、さらに機能が意味をなさない。変数エンドは、ローカル変数hのアドレスを格納するため

またはこれらの文

int h = mid-1; 
    end = &h; 

も意味がありません。

このデモプログラムでは、次のように機能を実装できます。

#include <iostream> 
#include <iomanip> 

bool binary_search(const int *begin, const int *end, int key) 
{ 
    if (begin < end) 
    { 
     const int *mid = begin + (end - begin)/2; 

     if (*mid < key) return binary_search(++mid, end, key); 
     else if (key < *mid) return binary_search(begin, mid, key); 
     else return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

int main() 
{ 
    int a[] = { 1, 3, 5 }; 
    const size_t N = sizeof(a)/sizeof(*a); 

    for (size_t i = 0; i <= a[N-1] + 1; i++) 
    { 
     std::cout << i << " is present in the array - " 
        << std::boolalpha << binary_search(a, a + N, i) 
        << std::endl; 
    } 

    return 0; 
} 

その出力は

0 is present in the array - false 
1 is present in the array - true 
2 is present in the array - false 
3 is present in the array - true 
4 is present in the array - false 
5 is present in the array - true 
6 is present in the array - false