I'm performing a binary search in an array, looking for a specific value inside of it. When I wrote the code the first time, my for loop for sorting the array in ascending order always added a 0 right in the middle of it so that I could not search for the last element of the array, since the middle part got now replaced with 0 and I don't know why, then I rewrote the program in the exact same way and suddenly it worked.
I noticed in the new rewritten program that when I write a for loop for iterating through the array and printing out its contents before the for loop for sorting the array that it adds a 0 in the middle again, if I delete that for loop everything works fine. I don't understand why that is, could somebody explain that to me please?
#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;
}
CodePudding user response：
This for loop
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;
}
}
invokes undefined behavior because there is an attempt to dereference memory outside the array when i is equal to Size - 1 in this if statement
if (Arr[i] > Arr[i 1])
{
Temp = Arr[i];
Arr[i] = Arr[i 1];
Arr[i 1] = Temp;
}
in the expression Arr[i 1].
You could rewrite the loop the following way
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;
}
}
The same problem can occur in this loop
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;
}
}
because the number of the loop iterations can be greater than required for the binary search method. As a result again Mid can have an invalid value as an index in the array.
CodePudding user response：
Don’t write using namespace std;.
You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)
int Temp, Size, Low = 0, High, Mid, Key, Found = 0;
Don't declare variables before they are ready to be initialized.
Don't gang together multiple variable declarations in one statement.
You don't actually need Temp (see later), and Found should be bool.
Temp = Arr[i];
Arr[i] = Arr[i 1];
Arr[i 1] = Temp;
Learn that there exists std::swap. In general, read through the <algorithms> to be familiar with what's available.
Size = (sizeof(Arr) / sizeof(Arr[0]));
Don't do that!
This is a C idiom that is fragile as it's very easy to accidentally use a value that decays to a pointer instead of getting the size of the array. There are direct ways to get this size in C , but you don't need it, because of the next point.
Instead of using subscripts, use iterators.
You can use the non-member functions begin and end with primitive arrays.
using std::begin;
using std::end;
auto low= begin(Arr);
auto high= end(Arr);
note that by convention (that is, everything in the standard library, the end is one past the end, not pointing at the last element.
In real life, you will call sort to sort the array, and then either upper_bound or lower_bound to do the binary search. But you are learning how the algorithm works, so you are implementing it yourself from scratch. You can, however, compare your result against the library function to test the results!
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;
}
A fully generic algorithm will be more careful and only use operations on the iterators that are universal, so it will work for anything not just primitive arrays. But it's starting to do things in the way of the standard library and following common conventions.
Postscript on array size
It's rare that you would need the obtain the size of a primitive array just on its own in the middle of other code. As I showed, you normally use begin and end as iterators, and don't care about the corresponding index values. Not all kinds of collections even have indexes like that!
It can be naturally picked up when passing a whole array using templates. For example,
template <typename T, size_t N>
void do_something (T (&arr)[N]) {
inside this function, N will have the array size.
There are standard functions to get the size though. Most directly, and specific to primitive arrays, is extent_v, so you could write:
size_t Size = std::extent_v<typeof(Arr)>;
which is awkward because you have a variable name (Arr) not a type name. But never fear, there is a more general function, the non-member size, that works for anything including arrays:
size_t Size = std::size(Arr);
that works OK because you know that Arr is in fact a primitive array. But it's not really kosher; you should write code to be general and generic, which, even if you're not writing a template, will greatly help maintenance. Changing the type of something is a common thing to do when editing the program to make improvements and fixes, and it's great when that "just works" and doesn't require other changes to be made to match!
The "std two-step" idiomatic usage
using std::size;
size_t Size = std::size(Arr);
The C 20 update
But the issues requiring the "std two-step" are now incorporated into the standard library, so on a newer compiler you can instead use:
size_t Size = std::ranges::size(Arr);
and it always works, for primitive arrays, collections defined in std, and other collection classes as well.