c++ - C++ 中的二进制搜索 : Ascending + Descending Ordered Arrays

Question

因此，我正在尝试为我的 C++ 类创建一个二进制排序算法，但是当我的 binarySearch 函数运行时，我一直遇到段错误。无论我和我的室友怎么看，我们都找不到问题所在。任何帮助将不胜感激。

int binarySearch(int arr[], int k, int first, int last)
{
    if(arr[first] <= arr[last])
    {
        int mid = (first + last) / 2;

        if(k == arr[mid])
        {
            return mid;
        }
        else if (k < arr[mid])
        {
            return binarySearch(arr, k, first, mid-1);
        }
        else return binarySearch(arr, k, mid+1, last);
    }   
    else if(arr[first] >= arr[last])
    {
        int mid = (first + last) / 2;

        if(k == arr[mid])
        {
            return mid;
        }
        else if (k < arr[mid])
        {
            return binarySearch(arr, k, mid+1, last);
        }
        else return binarySearch(arr, k, first, mid-1);
    }
    else return -1;
}

修复段错误后，我注意到我的逻辑中一定有错误，因为程序一直输出无法找到键，即使它存在于数组中。

Answer 1

如果您要搜索的元素在数组中，您的代码实际上可以工作。但是，它不会捕获不正确的输入。

调用函数时，请确保:

• first和 last介于 0 和(数组长度 - 1)之间
• first < last

例如:如果数组有 10 个元素，则 first 和 last 必须介于 0 和 9 之间。

尝试 this :

int main() {
    int a[] = {134, 232, 233, 234, 587, 623, 793, 802, 963, 1074};
    int b[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int na = binarySearch(a, 587, 0, 9);
    int nb = binarySearch(b, 3, 0, 9);

    printf("na: %d\n", na);  // prints 'na: 4'
    printf("nb: %d\n", nb);  // prints 'nb: 7'
}

如果您要搜索的元素不在数组中，那么递归永远不会终止，您可以通过将以下内容添加到 binarySearch() 的头部来解决这个问题:

if (first == last && k != arr[first])
    return -1;