C++ Linear search algorithm, determining the number of elements in array

Question

This code is from the Geeks for Geeks Algorithms section and i do not understand this part

int n = sizeof(arr) / sizeof(arr[0]);

In the main function, specifially why the division with sizeof(arr[0]) which would lead to half the number of actual elements in the array. Hope someone can explain me this.

// C++ code to linearly search x in arr[]. If x 

// is present then return its location, otherwise 
// return -1 

#include <iostream> 
using namespace std; 

int search(int arr[], int n, int x) 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 

int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = search(arr, n, x); 
(result == -1)? cout<<"Element is not present in array"
                : cout<<"Element is present at index " <<result; 
return 0; 
}

Vlad from Moscow · Accepted Answer · 2020-06-08T11:33:30.063

Let's consider the declared array

int arr[] = { 2, 3, 4, 10, 40 };

As the size of the array is not specified then the number of elements in the array is equal to the number of initializers.

It is not difficult to count the number of elements. It is equal to 5. So the array consists from 5 elements of the type int.

The memory allocated to the array is equal to 5 * sizeof( int ). it is the same as 5 * sizeof( arr[0] ) because the element arr[0] has the type int.

so you have that the size of the whole arrau is

sizeof( arr ) = 5 * sizeof( arr[0] )

Having this formula it is easy to determine the number of elements in the array having its size and the size of stored elements. That is

5 = sizeof( arr ) / sizeof( arr[0] )

So having an arbitrary array arr you can determine the number of elements the following way

N = sizeof( arr ) / sizeof( arr[0] )

The function search expects that the second argument will specify the number of elements in the passed array

int search(int arr[], int n, int x);

And it is calculated as shown above that is

int n = sizeof(arr) / sizeof(arr[0]); 
int result = search(arr, n, x);

If you compiler supports the C++ 17 Standard then instead of using this formula you could use the standard function std::size like

int result = search(arr, std::size( arr ), x);

Pay attention to that the function declaration and definition is bad.

For example the expression sizeof(arr) / sizeof(arr[0]) has the type size_t but the corresponding function parameter has the type int. The type int can be not enough large to store values of the type size_t. Secondly as the array is not being changed in the function then the first parameter shall have the qualifier const.

The function can be declared and defined the following way

size_t search( const int arr[], size_t n, int x) 
{
    size_t i = 0;

    while ( i != n && arr[i] != x ) ++i;

    return i;
}

If the target value is not found in the array then the function returns the size of the array that is n.

Pay attention that there is standard algorithm std::find that can be used instead of the function.

Ajanyan Pradeep · Answer 2 · 2020-12-29T12:23:58.307

6

sizeof() returns the memory used by the element.

Lets assume c++ uses x bytes for int.

So int array with 5 element will be of size 5x.

sizeof(arr) returns the memory used by integer array with 5 elements which is 5x.

sizeof(arr[0]) returns the memory used by integer which is x.

So sizeof(arr) / sizeof(arr[0]) will return 5 as the size

edited Dec 29 '20 at 12:23

answered Jun 07 '20 at 18:43

Ajanyan Pradeep

1,097
1
16
26

Allthough `int` would be allowed to be only 2 bytes wide, on most modern systems it's 4 bytes. Good answer otherwise. – Lukas-T Jun 07 '20 at 18:57
1

The answer is correct, but you could avoid using any particular size for `int`, and get the same result. – cigien Jun 07 '20 at 18:58
Thank you, got it! – Buggorilla Jun 07 '20 at 19:01
1

@cigien Thanks for the suggestion. Updated my answer. – Ajanyan Pradeep Jun 07 '20 at 19:08
@churill Updated my answer. Thanks – Ajanyan Pradeep Jun 07 '20 at 19:11

score 1 · Answer 3 · edited Jun 20 '20 at 09:12

The statement int n = sizeof(arr) / sizeof(arr[0]); is used to find the number of elements in arr.

How It Works ?

sizeof(arr) - This will return the amount of memory used by arr in bytes. In our case, arr is an array and so the expression will return the size occupied by arr in bytes.
sizeof(arr[0]) - This will also return the amount of memory stored by arr[0](Note : its not arr) . In our case, arr[0] is an element of array and so the expression will return the size occupied by arr[0] in bytes.
Now, the sizeof(arr) / sizeof(arr[0] will return the number of elements in the array. How? - The sizeof(arr) gave us total size of array in bytes and sizeof(arr[0]) gave us the size of just 1 element. So dividing them, we get the number of elements in our array.

NOTE : the size of each element will be same, so it is not that you only have to choose arr[0]. You could have chosen arr[3] or any other index given it was within array bounds

Hope this clears your doubt !

C++ Linear search algorithm, determining the number of elements in array

3 Answers3

How It Works ?