Array empty when passed to function

Question

I have the following code that is doing a binary search based on array and value to look for that is passed to function. However, when I step into the function, the array has no values. Why is this happening? I have looked and I believe everything is correct in terms of passing the array.

 #include <iostream>
using namespace std;

int binSearch(int [], int , int , int);

void main()
{
    int a[10];
    int low;
    int high;
    int searchValue;

    for (int i = 0; i < 10; i++)
    {
        a[i] = i;           
    }

    low = 0;
    high = 9;
    searchValue = 6;
    int searchResult = binSearch(a, low, high, searchValue);
    cout << searchResult << endl;
}

int binSearch(int a[], int low, int high, int searchValue)
{
    int newHigh;

    newHigh = (low + high) / 2;

    if (low > high)
    {
        return -1;
    }

    else if (high == low)
    {
        if (a[high] == searchValue)
        {
            return high;
        }

        else
        {
            return -1;
        }
    }

    else if (a[newHigh] < searchValue)
    {
        return binSearch(a, low, newHigh, searchValue);
    }

    else
    {
        return binSearch(a, newHigh, high, searchValue);
    }
}

The array is assigned values with the for loop and is then passed. When debugging, when it steps into binSearch the array contains nothing... so algorithm aside, it still has nothing... — cb1295, Mar 27 '14 at 08:10
How are you inspecting the array to determine it is empty? Are you printing it out, using an IDE (such as visual studio), or by some other manner? — Peter Clark, Mar 27 '14 at 08:11
I am using visual studio debug and when I hover over the array int the main function before going into binSearch, I see that it has the values I put it in. I then step into binSearch and then when I hover over the array it has no values stored — cb1295, Mar 27 '14 at 08:13
The "array" in binSearch is not an array. It is a pointer. You need to change how you're inspecting the values. — PaulMcKenzie, Mar 27 '14 at 08:15
Thanks @MariusBancila, you are right and now that I've got the main issue figured out I will fix — cb1295, Mar 27 '14 at 08:26

score 4 · Accepted Answer · edited May 23 '17 at 10:26

4

When you pass an array into a function it is said to "decay" into a pointer. Arrays in C++ are second class citizens and any time you pass them somewhere they are automatically converted into a pointer to the first element. This means that when you inspect the "array" inside the function, you're actually viewing the value of the first element (since an the array decays to a pointer to the first element).

One way you can inspect it as an array at this point is to add it to the watch window (right click -> Add Watch, or type the variable name in watch window) and put a comma next to it along with the size of the array.

For example typing a, 10 in the watch window while in your bin_search function would display the first 10 elements pointed to by a.

edited May 23 '17 at 10:26

Community

1
1

answered Mar 27 '14 at 08:17

Peter Clark

2,863
3
23
37

1

Thanks, that helped. I changed the argument to be `(&a)[10]` and it works perfectly. The algorithm just needs to be changed now as it is incorrect as pointed out above. – cb1295 Mar 27 '14 at 08:26
What do you mean by you "changed the argument to be `(&a)[10]`", I'm not quite certain I understand what you mean. – Peter Clark Mar 27 '14 at 08:37
1

No, I made it `int binSearch(int (&a)[10], int , int , int)` This helped me understand the issue of why I thought it wasn't getting passed when in reality what was happening was the "decay" you described. I now realize, with your help and that of the answer below, that the real issue was with the algorithm in terms of why I wasn't getting the result I was supposed to. – cb1295 Mar 27 '14 at 08:42
1

@PeterClark: "when you pass an array into a function it is said to "decay"" - more precisely, it's when an array is passed to a function argument of type `int*`, combined with the Standard mandating that all `int[]` arguments be handled as `int*`s, that kicked in here to cause decay. You can pass an array into a function without decay if the function accepts it as such, e.g.: `void f(int (&x)[4])` - but then the size must match perfectly (though `template void f(int (&x)[N])` is legit). Need C.T. const size. Whether that would help VS debugger I don't know, but I suspect it would. – Tony Delroy Mar 27 '14 at 08:46
Ah ok, I hadn't seen the syntax for a [reference to an array](http://stackoverflow.com/questions/5724171/passing-an-array-by-reference) before, and wasn't aware it prevented decay, though that makes sense now - thanks! – Peter Clark Mar 27 '14 at 08:46
1

@TonyD The VS debugger does recognize using a reference to an array and it gives the desired results (just tested it with VS2012). – Peter Clark Mar 27 '14 at 08:49
@PeterClark: oh cool - thanks for letting me/us know. Cheers. – Tony Delroy Mar 27 '14 at 09:14

score 1 · Answer 2 · edited Mar 30 '14 at 10:36

1

The array is fine. main() should return int in C++ and the binary search algorithm needed correction.

#include <iostream>
using namespace std;

int binSearch(int [], int , int , int);

int main()
{
    int a[10];
    int low;
    int high;
    int searchValue;

    for (int i = 0; i < 10; i++)
    {
        a[i] = i;
    }

    low = 0;
    high = 9;
    searchValue = 6;
    int searchResult = binSearch(a, low, high, searchValue);
    cout << searchResult << endl;
    return 0;
}

int binSearch(int a[], int low, int high, int searchValue)
{
    int mid;

    mid = (low + high) / 2;

    if (low > high)
    {
        return -1;
    }

    if (a[mid] == searchValue)
    {
        return mid;
    }    
    else if (a[mid] < searchValue)
    {
        return binSearch(a, mid+1, high, searchValue);
    }    
    else
    {
        return binSearch(a, low, mid-1, searchValue);
    }
}

edited Mar 30 '14 at 10:36

honk

9,137
11
75
83

answered Mar 27 '14 at 08:27

stakri

1,357
1
11
14

Thank you so much! It was the algorithm all along that was giving me -1 because it was going into the wrong branch. However, I did also learn that that what is passed is pointer to first element, which is why I would see zero when I looked at it in debug. – cb1295 Mar 27 '14 at 08:40
for the else, it shouldn't be `mid-1` in the recursive call, it should just be `mid`. This is because of the way integer division works and if you were to try searching for the middle it wouldn't work as it was before. Otherwise all works well, thanks. – cb1295 Mar 27 '14 at 08:53

score 0 · Answer 3 · answered Mar 27 '14 at 08:41

0

just change int binSearch(int a[], int low, int high, int searchValue) to

int binSearch(int* a, int low, int high, int searchValue)

answered Mar 27 '14 at 08:41

Idan Yehuda

524
7
21

1

Both the function signatures you suggest are equivalent. Arrays are naturally decayed into pointers. Also, there is nothing wrong with using the array syntax to indicate that a parameter is an array. – Peter Clark Mar 27 '14 at 08:42

Array empty when passed to function

3 Answers3