Binary search optimisation

user_13403510 0
Viewed 74

I implemented binary search in two ways and wondering which is more efficient? please help me know which is more efficient and how can it further be optimized? is time complexity remains same in both approach? I am a beginner in programming.

approach 1;

#include<iostream>
using namespace std;
bool BinarySearch(int*a,int n,int s ){
    if(n==1){
        if(a[0]==s)
            return true;
        else
            return false;
    }
    else{
        if(s<a[n/2]){
            int U[n/2];
            for(int i=0;i<n/2;i++){
                U[i]=a[i];
            }
            return BinarySearch(U,n/2,s);
        }
        else{
            int V[n-n/2];
            for(int i=0;i<n-n/2;i++){
                V[i]=a[i+n/2];
            }
            return BinarySearch(V,n-n/2,s);
        }

    }
}
int main(){
int array[10]={2,4,6,8,10,12,14,16,18,22};
cout<<BinarySearch(array,10,9);
}

approach 2:

#include<iostream>
using namespace std;
    bool Bsearch(int arr[],int s,int l,int x){
        cout<<"calling bsearch with arguments "<<s<<' '<<l<<' '<<x<<endl;
        if(l==1)
            return arr[s]==x;
        int h=l/2;
        if(x<arr[s+h])
            return Bsearch(arr,s,h,x);
        else
            return Bsearch(arr,s+h,l-h,x);
    }
int main(){
    int marks[11]={17,18,20,22,24,26,28,30,32,34,36};
    cout<<Bsearch(marks,0,11,32);
}

Thanks in advance for the kind help.

search arrays algorithm c++
1 Answers

Other posters are correct that variable-length arrays are not good C++. If you define your main() as:

int main() {
    std::array<int> marks{17,18,20,22,24,26,28,30,32,34,36};
    cout<<Bsearch(marks,0,32);
}

or:

int main() {
    std::vector<int> marks{17,18,20,22,24,26,28,30,32,34,36};
    cout<<Bsearch(marks,0,32);
}

then you can drop the pointer/length pair in the parameter list to your binary-search function. The function prototype becomes something like:

bool Bsearch(const std::array<int>& arr, int s, int x);
user_161752520
Related