0

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;
}
Vishal Singh
  • 725
  • 7
  • 16
  • 1
    Are you compiling as C or C++? The answers will be quite different for the two languages. – aschepler Jan 10 '20 at 19:18
  • 1
    @Dead Pool Calculate how much space your array occupies. And take into account that variable length arrays is not a standard C++ feature. – Vlad from Moscow Jan 10 '20 at 19:18
  • 2
    *Upto 999999 works fine but 9999991 gives segmentation fault.* Is this a typo? `999999` and `9999991` differ by `8999992`. – Fiddling Bits Jan 10 '20 at 19:19
  • 3
    `long int limit=2000000000; long int arr2[limit];` -- This is not valid C++. Second, even if it were valid syntax, the stack memory has been blown to bits with this declaration. – PaulMcKenzie Jan 10 '20 at 19:28
  • 2
    Your code is not valid C++: long int arr2[limit]; --> C++ doesn't support variable length arrays. – SurvivalMachine Jan 10 '20 at 19:29
  • 1
    I downvoted because this question can't be answered. C and C++ are different languages that behave differently. In C this code is valid and in C++ it isn't. – Thomas Sablik Jan 10 '20 at 19:48
  • Some of you pointed out, how noob it was of me to put C and C++ tags. Do suggest some good books for basics of C and C++. – Vishal Singh Apr 20 '20 at 06:20

1 Answers1

1

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;

user1669844
  • 703
  • 9
  • 23
  • 1
    Prefer a `std::vector` to `new`ing an array where possible. `vector` looks after itself much better than a raw dynamic array. In general, [Why should C++ programmers minimize use of 'new'?](https://stackoverflow.com/questions/6500313/why-should-c-programmers-minimize-use-of-new) – user4581301 Jan 10 '20 at 19:49