数组中的二进制搜索在以完全相同的方式重写后工作
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’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
中定义的集合以及 其他 集合 类。
我正在数组中执行二进制搜索,在其中查找特定值。当我第一次编写代码时,用于按升序对数组进行排序的 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’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
中定义的集合以及 其他 集合 类。