数组中的二进制搜索在以完全相同的方式重写后工作

Question

我正在数组中执行二进制搜索，在其中查找特定值。当我第一次编写代码时，用于按升序对数组进行排序的 for 循环总是在它的中间添加一个 0，这样我就无法搜索数组的最后一个元素，因为中间部分现在被替换了用 0 并且我不知道为什么，然后我以完全相同的方式重写了程序，突然它起作用了。

我注意到在新的重写程序中，当我编写一个 for 循环来遍历数组并在 for 循环之前打印出它的内容来对数组进行排序时，如果我删除它，它会再次在中间添加一个 0 for循环一切正常。我不明白这是为什么，有人可以向我解释一下吗？

#include <iostream>

using namespace std;

int main()
{
    int Arr[] = {1,-1,2,-2, 3,-3,4,-4,5,-5,6,-6,7,-7};
    int Temp, Size, Low = 0, High, Mid, Key, Found = 0;
    Size = (sizeof(Arr) / sizeof(Arr[0]));
    High = Size - 1;

    cout<<"Enter value of key you want to testsearch for:\n";
    cin>>Key;
/*
    for (int i = 0; i < Size; i++)     //if I don't comment out this loop the 0 will get added in
    {                                  //the middle of the array again and I don't know why
        cout<<Arr[i]<<" ";
    }
*/
    for (int Rep = 1; Rep <= Size-1; Rep++)
    {

        for (int i = 0, Temp = 0; i < Size; i++)
        {
            if (Arr[i] > Arr[i+1])
            {
                Temp = Arr[i];
                Arr[i] = Arr[i+1];
                Arr[i+1] = Temp;
            }
        }
    }

    for (int i = 0; i < Size; i++)
    {
        cout<<Arr[i]<<" ";
    }

    for (int i = 0; i < Size; i++)
    {
        Mid = (Low+High)/2;
        if (Arr[Mid] == Key)
        {
            Found = 1;
            break;
        }
        else if (Arr[Mid] < Key)
        {
            Low = Mid+1;
        }
        else if (Arr[Mid] > Key)
        {
            High = Mid-1;
        }
    }

    if (Found)
    {
        cout<<"\nGiven key value "<<Key<<" was found.";
    }
    else
    {
        cout<<"\nGiven key value "<<Key<<" was not found.";
    }

    return 0;
}

Answer 1

这个for循环

    for (int i = 0, Temp = 0; i < Size; i++)
    {
        if (Arr[i] > Arr[i+1])
        {
            Temp = Arr[i];
            Arr[i] = Arr[i+1];
            Arr[i+1] = Temp;
        }
    }

调用未定义的行为，因为在此 if 语句

中，当 i 等于 Size - 1 时，试图取消引用数组外的内存

        if (Arr[i] > Arr[i+1])
        {
            Temp = Arr[i];
            Arr[i] = Arr[i+1];
            Arr[i+1] = Temp;
        }

在表达式 Arr[i+1].

中

您可以按以下方式重写循环

    for (int i = 1; i < Size; i++)
    {
        if (Arr[i] < Arr[i-1])
        {
            int Temp = Arr[i];
            Arr[i] = Arr[i-11];
            Arr[i-1] = Temp;
        }
    }

在这个循环中也会出现同样的问题

for (int i = 0; i < Size; i++)
{
    Mid = (Low+High)/2;
    if (Arr[Mid] == Key)
    {
        Found = 1;
        break;
    }
    else if (Arr[Mid] < Key)
    {
        Low = Mid+1;
    }
    else if (Arr[Mid] > Key)
    {
        High = Mid-1;
    }
}

因为循环迭代的次数可以大于二进制搜索方法所需的次数。结果再次 Mid 可以有一个无效值作为数组中的索引。

Answer 2

Don’t写using namespace std;.

但是，您可以在 CPP 文件（而非 H 文件）或函数内部放置单个 using std::string; 等（参见 SF.7。）

int Temp, Size, Low = 0, High, Mid, Key, Found = 0;
不要在变量准备好初始化之前声明它们。
不要在一个语句中将多个变量声明组合在一起。

你实际上不需要Temp（见后面），Found应该是bool。

Temp = Arr[i];
Arr[i] = Arr[i+1];
Arr[i+1] = Temp;

得知存在std::swap。一般来说，通读 <algorithms> 以熟悉可用的内容。

Size = (sizeof(Arr) / sizeof(Arr[0]));
不要那样做！
这是一个脆弱的 C 习惯用法，因为很容易意外地使用一个衰减为指针的值而不是获取数组的大小。在 C++ 中有直接的方法来获得这个大小，但你不需要它，因为下一点。

不使用下标，而是使用迭代器。
您可以将非成员函数 begin 和 end 与原始数组一起使用。

using std::begin;
using std::end;

auto low= begin(Arr);
auto high= end(Arr);

请注意，按照惯例（即，标准库中的所有内容，end 是最后一个元素，而不是指向最后一个元素。

在现实生活中，你会调用sort对数组进行排序，然后调用upper_bound或lower_bound进行二分查找。但是你正在学习算法是如何工作的，所以你是从头开始自己实现它。但是，您可以将您的结果与库函数进行比较以测试结果！

while (low < high) {
   const auto dist = high-low;
   const auto mid = low+(dist/2);
   if (*mid == target)  return mid;
   if (*mid < target)  high=mid-1;
   else low=mid+1;
}

完全通用的算法会更加谨慎，并且只对通用的迭代器使用操作，因此它适用于任何东西，而不仅仅是原始数组。但它开始以标准库的方式并遵循通用约定来做事。

数组大小的后记

您很少需要在其他代码中间单独获取原始数组的大小。如我所示，您通常使用 begin 和 end 作为迭代器，并不关心相应的索引值。甚至不是所有类型的集合都有这样的索引！

当使用模板传递整个数组时，它可以自然地被拾取。例如，

template <typename T, size_t N>
void do_something (T (&arr)[N]) {

在此函数中，N 将具有数组大小。

虽然有标准函数可以获取大小。最直接且特定于原始数组的是 extent_v，因此您可以这样写：
size_t Size = std::extent_v<typeof(Arr)>;
这很尴尬，因为您有一个变量名 (Arr) 而不是类型名。但不要害怕，有一个更通用的函数，非成员size，它适用于包括数组在内的任何东西：

size_t Size = std::size(Arr);

可以正常工作，因为您知道 Arr 实际上是原始数组。但这并不是真正的犹太洁食；您应该编写通用和通用的代码，即使您不编写模板，也将极大地帮助维护。在编辑程序以进行改进和修复时，更改某些内容的类型是一件很常见的事情，当它“正常工作”并且不需要进行其他更改以匹配时，这很棒！

"std two-step" 惯用用法

using std::size;
size_t Size = std::size(Arr);

C++20 更新

但是需要“std 两步”的问题现在已合并到标准库中，因此在较新的编译器上您可以改用：

size_t Size = std::ranges::size(Arr);

并且它始终适用于原始数组、std 中定义的集合以及其他集合类。

数组中的二进制搜索在以完全相同的方式重写后工作

Binary search in an array works after rewriting it in the exact same way

c++

arrays

sorting

loops

binary-search

数组大小的后记

"std two-step" 惯用用法

C++20 更新