Can you explain this line of linear search algorithm?

Question

So what's this line means? int n = sizeof(arr) / sizeof(arr[0]) Why are we dividing arr with arr[0] and whats the use of n here?

#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;
}
 
// Driver code
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    int result = search(arr, n, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}

but you should use `std::vector` or range (iterator pair/span) — apple apple, May 29 '21 at 09:12

Vlad from Moscow · Answer 1 · 2021-05-29T10:23:36.580

From the C++ 14 Standard (5.3.3 Sizeof)

1 The sizeof operator yields the number of bytes in the object representation of its operand...

If you have an array declared for example like this

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

then the expression

sizeof( arr )

yields the size of the memory occupied by the whole array.

The expression

sizeof(arr[0])

is the size of each element of the array because all elements of an array has the same size. As the type of array elements is int then you could write also

sizeof( int )

instead of

sizeof( arr[0] )

So the expression

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

yields the number of elements in the array.

Here is a demonstrative program.

#include <iostream>

int main() 
{
    int arr[] = { 2, 3, 4, 10, 40 };
    
    size_t size_of_array = sizeof( arr );
    
    std::cout << "The size of the memory occupied by the array is " 
              << size_of_array << '\n';
              
    size_t size_of_element = sizeof( arr[0] );
    
    std::cout << "The size of the memory occupied by each element of the array is "
              << size_of_element << '\n';
              
    std::cout << "The number of elements in the array is "
              << size_of_array / size_of_element << '\n';
              
    return 0;
}

The program output is

The size of the memory occupied by the array is 20
The size of the memory occupied by each element of the array is 4
The number of elements in the array is 5

Pay attention to that the value of the expression has the type size_t instead of the type int.

If your compiler support C++ 17 then you can use standard function std::size declared in the header <iterator> instead of the expression sizeof( arr ) / sizeof( arr[0] ) like for example

#include <iterator>

//...

size_t n = std::size( arr );

As for the function search then it should be declared and defined like

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

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

    return pos;
}

and in main you should write

size_t pos = search(arr, n, x);
( pos == n )
    ? cout << "Element is not present in array.\n"
    : cout << "Element is present at index " << pos << '\n';

A mention of std::size as an abstraction of/replacement to this unreadable idiom would be a nice addition to your answer :) — spectras, May 29 '21 at 10:10

score 1 · Answer 2 · answered May 29 '21 at 09:13

That line determines the size of the array. In C/C++ arrays (in contrast to Java) the size is not available. Since an array of n elements uses n times the size of a single element, you can calculate the number of elements like this. This makes more sense when using templates where the actual size of an array element is unknown at compile time.

Can you explain this line of linear search algorithm?

2 Answers2