使用常量指针进行二进制搜索

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); 

从递归调用返回的结果。

Answer 2

在这些情况下，如果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); 
} 

该函数返回什么。那就是这些代码块没有返回语句。

另外的功能是没有意义的，因为，例如在这些语句

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

有比较与阵列，而不是与该元件的阵列中的值与指数中期比较关键的索引关键。

或者这些语句

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

也没有意义，因为变量年底将存储在本地变量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