C++ 中的二进制搜索：升序 + 降序有序数组

Question

所以我正在尝试为我的 c++ class 制作二进制排序算法，但是当我的 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

不是主要问题，但为了防止溢出，通常将 int mid = (first + last) / 2; 重写为 int mid = first + (last-first)>>1; 看起来你永远不会碰到 return -1 行（前两个条件语句处理所有可能的排序）

一个实现（严格增加或减少数组）可能看起来像这样

#include <cassert>

int binarySearch(int* array, int k, int l, int h, bool asc)
{
    if (l>h)
        return -1;
    int m = l + ((h - l) >> 1);
    if (array[m] == k)
        return m;
    else
    {
        if (array[m]>k)
            return binarySearch(array, k, (asc ? l : m + 1), (asc ? m - 1 : h),asc);
        else
            return binarySearch(array, k, (asc ? m + 1 : l), (asc ? h : m - 1),asc);
    }
}

int main()
{
    int ascArray[7] = {1, 2, 3, 4, 5, 6, 7};
    int descArray[7] = {7, 6, 5, 4, 3, 2, 1};
    assert(binarySearch(ascArray, 7, 0, 6, ascArray[0] < ascArray[1]) == 6);
    assert(binarySearch(descArray, 7, 0, 6, descArray[0] < descArray[1]) == 0);
}

Answer 2

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

调用函数时，确保：

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;

Answer 3

而不是使用 if else if，你可以尝试 while 循环：

int mid = (first + last)/2;
while(first<=last && arr[mid]!=k){
    if(arr[mid]<k)
        first=mid+1;
    else
        last=mid-1;
    mid = (first + last)/2;

}
if(arr[mid] == k){
    std::cout<<"Found"<<std::endl;
}else{
    std::cout<<"Not Found"<<std::endl;
}

相反，您可以使用矢量，这非常简单：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){

int arrint[] = {3,5,2,1,7,6,9,4,8,10};
vector<int> vector1(arrint,arrint+10);

sort(vector1.begin(),vector1.end());
int n;
cout<<"Enter element to search: ";
cin>>n;
cin.ignore();
cout<<endl;

if(binary_search(vector1.begin(),vector1.end(),n)){
    cout<<"Found: "<<n<<endl;
}else{
    cout<<n<<" Not Found"<<endl;
}


//cin.get();
return 0;
}

Answer 4

确保first>=last。我认为崩溃是因为您没有在数组中找到该元素。

C++ 中的二进制搜索：升序 + 降序有序数组

Binary Search in C++: Ascending + Descending Ordered Arrays

c++

binary-search