CODEWITHSUNDEEP
csegmentation-faultbinary-searchlong-integer
Vishal Singh
Vishal Singh

Reputation: 801

segmentation fault above 999999 for cpp in long int

I have to find the time it takes to for binary search for numbers from 1 to 2 billion but i cant use the data types. long int or long long int or any other shows segmentation fault. Upto 999999 works fine but 9999991 gives segmentation fault. please help.

 void binSch2(long  int arr[], long int x, long int l, long int h)
 {

    if(l>h)
    {
        printf("not present");
        return;
    } 
    unsigned long  int mid=l+(h-l)/2;
    if(arr[mid]==x)
    {
        printf("found %ld at %ld", x, mid);
    }
    else if(x<arr[mid]) binSch2(arr, x, l, mid-1);
    else if(x>arr[mid]) binSch2(arr,x , mid+1, h);

 }

int main()
{

    long  int limit=2000000000;
    long  int arr2[limit];
    for(long  int i=0; i<limit; i++)
    {
        arr2[i]=i+1;
    }
    long  int N2=sizeof(arr2)/sizeof(arr2[0]);
    long  int x2=88888;
    long  int z=0;

    clock_t begin = clock();
    binSch2(arr2, x2, z, N2-1);
    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("\ntime : %lf ", (double)(end - begin) / CLOCKS_PER_SEC);

    return 0;
}

Upvotes: 0

Views: 270

Answers (1)

user1669844
user1669844

Reputation: 763

Try allocating memory in heap for arr2 variable as follow- see this

long int *arr2 = new long int[limit];

limited stack size is assigned for each function maybe(4k or 4M(large) pagesize) and local variables goes on the stack. So if you do the calculation, there is not enough space on stack for arr2 and program return access violation once it reach the stack limit. Also, don't forget to free the allocated space. delete [] arr2;

Upvotes: 1

Related Questions