C++线性搜索算法，判断数组元素个数

Question

这段代码来自 Geeks for Geeks Algorithms 部分，我不明白这部分

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

在主函数中，特别是为什么使用 sizeof(arr[0]) 的除法会导致数组中实际元素数量的一半。希望有人可以向我解释这一点。

// 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; 
}

Answer 1

让我们考虑声明的数组

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

由于未指定数组的大小，因此数组中的元素数等于初始值设定项的数量。

计算元素的数量并不难。它等于5。因此该数组由 5 个类型的元素组成int。

分配给数组的内存等于5 * sizeof( int )。这与5 * sizeof( arr[0] )因为元素arr[0]具有 type 相同int。

所以你有整个arrau的大小是

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

有了这个公式，很容易确定数组中具有其大小和存储元素大小的元素的数量。那是

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

因此，拥有任意数组，arr您可以通过以下方式确定元素数

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

函数搜索期望第二个参数将指定传递数组中的元素数

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

它的计算方式如上所示

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

如果编译器支持C ++ 17标准，然后，而不是使用这个公式，你可以使用标准的功能std::size像

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

注意函数声明和定义不好。

例如，表达式sizeof(arr) / sizeof(arr[0])具有类型，size_t但相应的函数参数具有类型int。类型int可能不够大，无法存储类型的值size_t。其次，由于函数中的数组未更改，因此第一个参数应具有 qualifier const。

可以通过以下方式声明和定义该函数

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

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

    return i;
}

如果在数组中未找到目标值，则该函数返回数组的大小为 n。

请注意，std::find可以使用标准算法代替函数。

Answer 2

sizeof() 返回元素使用的内存。

让我们假设c++使用 x 字节为int.

因此，int具有 5 个元素的数组的大小将是 5 倍。

sizeof(arr) 返回由 5 个元素的整数数组使用的内存，即 5x。

sizeof(arr[0]) 返回整数使用的内存，即 x。

所以sizeof(arr) / sizeof(arr[0])将返回 5 作为大小