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

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

我正在数组中执行二进制搜索,在其中查找特定值。当我第一次编写代码时,用于按升序对数组进行排序的 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;
}

这个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 可以有一个无效值作为数组中的索引。

Don’tusing 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++ 中有直接的方法来获得这个大小,但你不需要它,因为下一点。


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

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

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

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

在现实生活中,你会调用sort对数组进行排序,然后调用upper_boundlower_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;
}

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


数组大小的后记

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

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

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 中定义的集合以及 其他 集合 类。