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

到return递归调用的结果。

Answer 2

在这些 if 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);
}

函数return什么都没有。那就是这些代码块没有 return 语句。

此外，该函数没有意义，因为例如在这些语句中

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

将键与数组的索引进行比较，而不是将键与数组中索引为 mid 的元素的值进行比较。

或者这些语句

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

也没有意义，因为变量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

使用 const 指针进行二进制搜索

Binary searching using const pointer

c++

arrays

binary-search