无法找到数组的大小和输出问题

Question

我正在实施二进制搜索。但我不想将数组的大小作为参数传递给 binarySearch 函数。我试图在函数中找到数组大小。我用的是sizeof operator，但是二分查找的输出是错误的。当我尝试将数组的大小作为参数传递时，输出很好。我的问题是为什么以及在函数中计算数组大小的问题是什么？是否可以在函数中计算数组大小？

这是我的方法：

code

#include <bits/stdc++.h>
using namespace std;
void binarySearch(int arr[], int value)
{
   int c = sizeof(arr) / sizeof(arr[0]);
   
  //cout << c;
  int low = 0, high = c - 1, notFound = 1;

  while (low <= high)
  {
     int mid = (low + high) / 2;
     if (arr[mid] == value)
     {
        cout << "Found at index " << mid << endl;
        notFound = 0;
        break;
     }
     if (arr[mid] < value)
     {
        low = mid + 1;
     }
     else
     {
        high = mid - 1;
     }
   }

   if (notFound == 1)
   {
      cout << "Not Found" << endl;
   }
}
int main()
{
   int arr[] = {1, 2, 3, 4, 5, 6, 9, 56, 88};
   int x = 3;
   binarySearch(arr, x);
   //cout << p << endl;
}

输出：

 tempCodeRunnerFile.cpp:5:22: warning: 'sizeof' on array function parameter 'arr' will return size of 'int*' [-Wsizeof-array-argument]
    int c = sizeof(arr) / sizeof(arr[0]);
                      ^
tempCodeRunnerFile.cpp:3:23: note: declared here
 void binarySearch(int arr[], int value)
                   ~~~~^~~~~
Not Found

我的预期输出：

Found at index 2

Answer 1

My question is why & what is the problem for calculating array size in function

问题是 arr 是指向数组元素的指针。指针的大小与数组的大小无关，这就是为什么您尝试 sizeof(arr) 无法工作的原因。

警告信息也很好地解释了这一点。

is it possible to calculate array size in function?

只给定一个指向元素的指针，一般¹不可能确定数组的大小。这就是为什么您必须将大小作为参数传递的原因。

我更喜欢的另一种方法是将指针和长度封装在class中。有一个用于此目的的标准 class 模板：std::span.

void binarySearch(std::span<int> arr, int value)
{
   int c = arr.size();
   ...


// call as in your example:
int arr[] = {1, 2, 3, 4, 5, 6, 9, 56, 88};
int x = 3;
binarySearch(arr, x);

¹ 有一些技术可以做到这一点，但它们也有缺点。

一种技术是选择一个元素值作为“终止符”又名“哨兵”，表示数组的结尾。这样，您可以对终止符进行线性搜索以确定长度。这通常用于 C 中的字符串，其中空终止符终止字符串。如果您不能将任何值指定为终止符，则此技术不是一种选择。另一个明显的缺点是大小计算的线性复杂性，它比您正在实施的二进制搜索渐近地更昂贵

Answer 2

您还可以使用另一种可能性，但使用太多不同大小的数组调用它可能会导致代码膨胀。

template<std::size_t N>
void binarySearch(int arr[N], int value)

然后使用N代替c。

无法找到数组的大小和输出问题

Trouble to find size of an Array & Output issue

c++

algorithm

binary-search