Limit to Array Size?

[Grashopper]

So I'm doing a homework problem. We can code our solutions in Java or C++ (or both for extra credit). Our task for this project is to create a program that compares Linear Search through a sorted array to a Binary Search of the same array. I've done the program in Java (language I have most experience in), but when porting to C++ it run like a champ until it tries to make an array of 1,000,000 integers (it increments through array sizes of 10, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000). It makes it through the first 9 arrays no problem, but crashes when it hits 1,000,000. I know this b/c the file that I'm using as an output stops abruptly right where it should transition from 500,000 to 1,000,000. Is there a limit to the size an array can be that I missed somewhere? After coming this far, I'd really like to get this working the way it's supposed to.

The code when it exits is: dlight2\bin\nativeexecution\dorum.sh: line33: 4276 Segmentation fault (core dumped) sh "<$SHFILE>"

Any suggestions would be welcome. Code below.

#include <stdlib.h>
#include <iostream>
#include <fstream>
using namespace std;

bool LinearSearch(int A[], int n, int v){
    bool found = false;
    int work = 0;
    // Open the file and create a stream for writing
    ofstream out;
    out.open("linear++.csv", ios::app);
    // Start at the beginning of the array and search for value
    for (int s = 0; s < n; s++){
        work++;     // increment for the comparison (s < n)
        if (v == A[s]){
            work++; // increment for the comparison (v == A[s])
            found = true;
            cout << "Success! It took " << work << " work to find.\n";
            out << v << "," << work << "," << n << "\n";
            out.close();
            return found;
        }
    work++; // for incrementing the loop
    }
    return found;
}

bool BinarySearch(int A[], int n, int v){
    int first = 0;  // keeps the index for the start of the search range
    int upto = n;   // keeps the index for the end of the search range
    int work = 0;   // keeps track of comparisons, increments, and additions
    bool found = false;
    // Open the file and create a stream for writing
    ofstream out;
    out.open("binary++.csv", ios::app);
    // Binary Algorithm
    while (first < upto){
        work++;     // for the comparison (first < upto)
        int mid = (first + upto)/2;     // The midpoint of the array
        work++;     // Calculation of mid
        if (v < A[mid]){
            work++;     // for the comparison in the if statement
            upto = mid;
        } else if (v > A[mid]){
            work++;     // for the comparison in the else if statement
            first = mid + 1;
        } else {
            found = true;   // We found our number
            cout << "Success! It took " << work << " work to find\n";
            out << v << "," << work << "," << n << "\n";
            out.close();
            return found;
        }

    }
    return found;
}

int main() {
    // Create a file for the results
    ofstream lf ("linear++.csv");
    ofstream bf ("binary++.csv");
    // Create a header row for easy import to spreadsheet
    lf << "Value, Work, Size \n";
    bf << "Value, Work, Size \n";
    // Close the files
    lf.close();
    bf.close();

    cout << "Starting Search Comparison Program\n";
    // Set the array lengths in an array
    int N [] = {10, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000};
    cout << "N Values Loaded\n";
    // Loop 10 times, once for each integer in N
    for (int i = 0; i < 10; i++){
        // test array is the array that will be passed into the functions
        int test [N[i]];
        cout << "Intializing the test array\n";
        // Loop through the test array and create an ordered list
        for (int j = 0; j < N[i]; j++){
            test[j] = j;
        }
        cout << "Array initialized.\n";
        // Run the test of each search of N integers 100 times
        for (int l = 0; l < 100; l++){
            int value = (rand()%N[i]);
            cout << "The value I'm searching for is " << value << " \n\n";
            cout << "Starting the Linear Search Function\n";
            LinearSearch(test, N[i], value);
            cout << "Finished Linear Search\n";
            cout << "Starting Binary Search\n";
            BinarySearch(test, N[i], value);
            cout << "Finished Binary Search\n";
        }
    }
    return (EXIT_SUCCESS);
}

[jsmith]

You are putting all of that on the stack (line 77). You probably don't have enough
stack space for 4 million bytes of data. Try dynamically allocating the test array.

[Disch]

int test [N[i]];

Umm.. you can't do that anyway.

Do compilers actually allow that?

EDIT: holy crap... GCC lets you do it. Or at least it compiles okay (doesn't even give a warning!)

That just seems... wrong

[Duthomhas]

It is a compiler extension called a variable length array.
http://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html

It is permissible in C99, but not in C89 or C++.

I would recommend using a std::deque instead of an array. It handles memory better.

Hope this helps.

[harini1111]

Allocate those arrays are in Dynamically.

[Grashopper]

I don't know much about std::deque (this is my 2nd program in C++ ever).. I'll look it up and see if I can use that.