How To detect an empty C-array passed with wrong size?

Question

I have a binarysearch function with interface as follows:

bool binarysearch(int* array, int size, int findnum) {
    doBinarySearch(array, 0, (size-1), findnum);
}

The code for doBinarySearch is:

bool doBinarySearch(int* array, int start, int end, int findnum) {  
    if (end <= start)
        return false;

   int mid = (start+end)/2;
   if (array[mid] == findnum) {
       return true;
   } else if (findnum < array[mid]) {
       return doBinarySearch(array, start, mid, findnum);
   } else {
       return doBinarySearch(array, mid+1, end, findnum);
   }
}

I wrote a unit test to test the above function. If I call binarysearch with empty array and wrong size from main, the code seg. faults as expected. E.g.

int main() {  
    int *array;  
    binarysearch(array, 10, -1);    
}

But if I write a unit test class and have a function which does the above, then the binary search does not crash. Any idea, why the different behavior:

class TestBinarySearch {
    public:
        void testEmptyArray() {
            int *array;
            binarysearch(array, 10, -1);
        }
 };

 int main() {
     TestBinarySearch testObj;
     // below line does not cause seg fault. and -1 is found for some reason
     testObj.testEmptyArray(); 
 }

Another question - Is there any way to detect the seg. fault if somebody calls the function with wrong size? I see some examples of using signals to catch that, but after that except exiting the program, can anything else be done?

Indexing an array outside of the allocated space is undefined behavior. You could find -1 or 0 or 99999999 or the color blue. It is undefined behavior. — Cory Kramer, Aug 20 '14 at 00:10
@Cyber - thanks, but why does not second code always has defined behavior of not crashing. Is there any compilation flag which can change this? — cppcoder, Aug 20 '14 at 00:11
possible duplicate of [C++ Accesses an Array out of bounds gives no error, why?](http://stackoverflow.com/questions/1239938/c-accesses-an-array-out-of-bounds-gives-no-error-why) — Cory Kramer, Aug 20 '14 at 00:12
The way to detect this is to pass something that knows its size. Don't make the caller do extra work. Also, `std::binary_search`. — chris, Aug 20 '14 at 00:14
"why does not second code always has defined behavior of not crashing" -- because, as Cyber said, the behavior is **undefined**. That means there's no specification of how it behaves, so it might crash or might not. It's a mistake to interpret "undefined behavior" to mean that the program won't work ... it might work or not; the behavior is **undefined**. So your goal is unachievable ... you cannot write tests for undefined behavior, only for defined behavior. — Jim Balter, Aug 20 '14 at 03:01

score 2 · Answer 1 · answered Aug 20 '14 at 00:12

Both ways of writing it invoke undefined behavior. And undefined behavior can be anything. That it crashes in one you should be grateful for; that it "succeeds" in the other is unfortunate but very possible. The behavior might even change next time you reboot your computer or run the program, who knows. It's undefined.

If you're on Linux, run both programs under valgrind and see what it says. It may report errors even when there is no crash.

score 2 · Answer 2 · answered Aug 20 '14 at 00:34

Reading beyond the end of an array is undefined behaviour, as John has said. The compiler can do whatever it likes; your software may crash, it may process rubbish data, it may reformat your hard drive (at least in standards conformance terms).

There is no way to detect that the wrong size for the array has been given.

The right way to fix this is to pass in one of the STL containers and not a C array. At a minimum, you could rewrite the binarySearch function like this:

bool binarysearch(std::vector<int> array, int findnum) {
    doBinarySearch(&array[0], 0, array.size()-1, findnum);
}

score 2 · Answer 3 · answered Aug 20 '14 at 02:03

This situation is not an empty array, this is an unitialised pointer variable. Dereferencing an uninitialised pointer is Undefined Behaviour. It's a program error, and you cannot protect against it.

Undefined Behaviour means that anything might happen. Crash one time, not another, it's all as expected.

With this API both your caller and your unit test must ensure that the array passed is valid and at least as long as the length passed, and there is absolutely no way to programmatically check that this is so.

You could consider changing the API to use an STL collection instead, but that would be a different question.

BTW you have an unrelated bug. The code should say:

if (end < start) return false;

How To detect an empty C-array passed with wrong size?

3 Answers3