时间戳

首页 > 解决方案 > 递归二进制搜索中的分段错误

c++ - 递归二进制搜索中的分段错误

问题描述

我想多次使用相同的函数进行二进制搜索，但它显示分段错误。对于一个输入，它给出了正确的答案，但是当我为二进制搜索提供多个输入（即，q>1 acc. to my code）时，它会显示分段错误。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int binarySearch(int x[],int l, int r, long int m ){
    if(r>=1){
        int mid=(r-1)/2+l;
        if (x[mid]==m) return mid;
        if (x[mid]>m) return binarySearch(x,l,mid-1,m);
        if (x[mid]<m) return binarySearch(x,mid+1,r,m);
    }
    return 0;
}
int main(){
    int n,q;
    cin>>n;
    int x[n];
    for(int i=0;i<n;i++){cin>>x[i];}
    int t = sizeof(x) / sizeof(x[0]);
    sort(x,x+t);
    cin>>q;
    while (q--){
        long int m;
        cin>>m;
        cout<<binarySearch(x,0,t-1,m)<<endl;
        
    }
    
    
    
    return 0;
}

标签： c++

解决方案

  • 条件r>=1应该是r-l+1>=1检查范围内是否有一些元素。
  • 初始化int mid=(r-1)/2+l;应该是int mid=(r-l)/2+l;正确计算中间元素。
  • 可变长度数组int x[n];不在标准 C++ 中。您应该改用堆分配int *x = new int[n];。之后，n应该用于初始化，t因为获取数组中元素数量的技术不适用于指针。
#include <iostream>
#include <algorithm>
using namespace std;

int binarySearch(int x[],int l, int r, long int m ){
    if(r-l+1>=1){
        int mid=(r-l)/2+l;
        if (x[mid]==m) return mid;
        if (x[mid]>m) return binarySearch(x,l,mid-1,m);
        if (x[mid]<m) return binarySearch(x,mid+1,r,m);
    }
    return 0;
}
int main(){
    int n,q;
    cin>>n;
    int *x = new int[n];
    for(int i=0;i<n;i++){cin>>x[i];}
    int t = n;
    sort(x,x+t);
    cin>>q;
    while (q--){
        long int m;
        cin>>m;
        cout<<binarySearch(x,0,t-1,m)<<endl;
        
    }
    
    
    delete[] x;
    return 0;
}

推荐阅读