binary search on array based list

[zfareed]

<code>
#include <iostream>
#include <fstream>

const int MAX_LENGTH = 10;

using namespace std;



class IntList
{
public:
IntList();
void GetList(ifstream &data);
void PrintList();
int LengthIs();


private:

int length;
int values[MAX_LENGTH];
};

bool BinarySearch(IntList [], int , int , int ,bool);

int main()
{
ifstream inData;
IntList info;
int item,fromLoc,toLoc,istep=0;
bool found = true;
char answer;

string msg = "Number out of range! ";
inData.open("int.dat");
do{
cout << fixed << showpoint;
cout << "Enter value to be searched for: "<< endl;
cin >> item;
cout << "Enter starting location in 0-9 range: "<< endl;
cin >> fromLoc;
cout << "Enter end location in 0-9 range: "<< endl;
cin >> toLoc;
try{
while(istep != MAX_LENGTH)
{
if((fromLoc <= 9) && (fromLoc >=0)&&(toLoc <= 9) &&
(toLoc >=0) && (fromLoc<toLoc))
{ cout << "Correct range! Do the search." <<endl;
BinarySearch(info,item,fromLoc,toLoc,found);
istep++;
cout << "This is the " << istep <<"th iteration,
do you want to continue? <Y/N> ";
cin >> answer;
if(answer == 'n')
{ cout << "Search abrted!";
break;
}
}
else
throw msg;

}
}
catch(string message)
{
cout << message << "Search aborted!";

}
break;

}while(found = false);



cout << endl;
cout << "*******************************************************"
<< endl;

info.GetList(inData);
cout << "The list is : ";
info.PrintList();
cout << endl;
cout << "Length is " << info.LengthIs() << endl;
cout << "*******************************************************"
<< endl;
system("pause");
return 0;

}

IntList::IntList()
{
length =0;
}

void IntList::GetList(ifstream &data)
{
int value;

data >> value;

while(data)
{
for(int i=0;i<MAX_LENGTH;i++)
{
data >> value;
values = value;
length++;
}
cout << "List has been populated." << endl;
}

}

void IntList:rintList()
{
int index;
for(index=0;index<MAX_LENGTH;index++)
{
cout << values[index]<< " ";
}
}



int IntList::LengthIs()
{
return length;
}

bool BinarySearch(IntList info[], int item, int first, int last,bool
found)
{
int mid;
found = false;
int num = 1;
while(first <= last)
{
mid = (first + last) / 2;
if(item > info[mid])
first = mid +1;
else if(item < info[mid])
last = mid - 1;
else

return found = true;



}
return found = false;
}

</code>

I am passing an array based list to a function to perform a binary
search for an item being inputted. I get these compilation errors:

50 D:\ cannot convert `IntList' to `IntList*' for argument `1' to
`bool BinarySearch(IntList*, int, int, int, bool)'
D:\ In function `bool BinarySearch(IntList*, int, int, int, bool)':
137 D:\
no match for 'operator>' in 'item > *((+(((unsigned int)mid) * 44u)) +
info)'

 

[Victor Bazarov]

<code>
[..]
class IntList
{ [..]
};

bool BinarySearch(IntList [], int , int , int ,bool);

So, the first argument is an array of IntList? Or is it a pointer
to IntList? What is it? I believe you actually wanted to pass
your IntList by _reference_, but somehow got confused by all the
"array based" smokescreen. No matter. Your declaration here is

bool BinarySearch(IntList*, int, int, int, bool);

so the first argument is a pointer.

int main()
{
ifstream inData;
IntList info;

'info' is an _object_ of type 'IntList'.

[..]
BinarySearch(info,item,fromLoc,toLoc,found);

And here you're passing your object when the function actually
expects a pointer. You probably want to do

BinarySearch( & info , ...

[..]

</code>

I am passing an array based list to a function to perform a binary
search for an item being inputted. I get these compilation errors:

50 D:\ cannot convert `IntList' to `IntList*' for argument `1' to
`bool BinarySearch(IntList*, int, int, int, bool)'

Right. See above for the correction.

D:\ In function `bool BinarySearch(IntList*, int, int, int, bool)':
137 D:\
no match for 'operator>' in 'item > *((+(((unsigned int)mid) * 44u)) +
info)'

I have no idea what that is. Which like was 137? I am kinda lazy
to count to 137.

V

 

[zfareed]

Thank you for your response. I made the changes but I still dont
understand the called function and the errors:
Do I have to declare a pointer or just pass it to the function?
<code>
bool BinarySearch(IntList &info, int item, int first, int last,bool
found)
{
int mid;
found = false;
int num = 1;
while(first <= last)
{
mid = (first + last) / 2;
if(item > info[mid]) //line producing error
first = mid +1;
else if(item < info[mid])
last = mid - 1;
else

return found = true;
}
return found = false;
}


bool BinarySearch(IntList *, int , int , int ,bool);//prototype


Please help
BinarySearch(&info,item,fromLoc,toLoc,found); // function being called
in main


</code>

137
no match for 'operator[]' in 'info[mid]'

 

[Victor Bazarov]

Thank you for your response. I made the changes but I still dont
understand the called function and the errors:
Do I have to declare a pointer or just pass it to the function?
<code>
bool BinarySearch(IntList &info, int item, int first, int last,bool

found)
{
int mid;
found = false;
int num = 1;
while(first <= last)
{
mid = (first + last) / 2;
if(item > info[mid]) //line producing error
first = mid +1;
else if(item < info[mid])
last = mid - 1;
else

return found = true;
}
return found = false;
}


bool BinarySearch(IntList *, int , int , int ,bool);//prototype

Your prototype does not match the definition.

Please help
BinarySearch(&info,item,fromLoc,toLoc,found); // function being called
in main


</code>

137
no match for 'operator[]' in 'info[mid]'

Well, since you haven't defined (overloaded) the operator[] for the
'IntList' class, what do you want? You can't use 'info[mid]' unless
you define the operator[] in 'IntList'.

V

 

[Ralph D. Ungermann]

class IntList
{
public:
IntList();
void GetList(ifstream &data);
void PrintList();
int LengthIs();

There is no method to read the i'th list member. You need

int get( int pos ) const;
or
int operator[] ( int pos ) const;

bool BinarySearch(IntList info[], int item, int first, int last,bool
found)
{ [snipped]
if(item > info[mid])

D:\ In function `bool BinarySearch(IntList*, int, int, int, bool)':
137 D:\
no match for 'operator>' in 'item > *((+(((unsigned int)mid) * 44u)) +
info)'

1. info[mid] has type IntList; that's probably not what you intended,
but it's legal code.

2. You try to compare an int with an IntList; the compiler has many
operator > () available, but none of them matches ( int, IntList ).
That's what the compiler is trying to tell you.

3. Unfortunately, the message prints a simple "a" as something like
"*( i*sizeof(a) ) + a". That's a very special, internal notation.
A better message would have been:

> no match for 'operator>( int, IntList )' in 'item > info[mid]'

Maybe it's time to upgrade your compiler.



More comments on your function BinarySearch():

- it needs a single IntList (no array of), and doesn't modify it. So
just write "IntList const &info" (or "const IntList &info", which is the
same). Then you can refer to its elements via "info.get(mid)" or
"info[mid]", or whatever you defined in class IntList.

- The arguments `item' and `found' are passed by value. Your assignments
have no effects to the caller.

 

[zfareed]

I'm sorry guys; could anyone spell this out to me like I'm a ten year
old. I dont understand operator overloading and when you say reading
the list, do I just use a for loop to read the list and then implement
the comparisons?
<code>
#include <iostream>
#include <fstream>

const int MAX_LENGTH = 10;

using namespace std;



class IntList
{
public:
IntList();
void GetList(ifstream &data);
void PrintList();
int LengthIs();
int operator[](int mid);
private:

int length;
int values[MAX_LENGTH];
};

bool BinarySearch(IntList *, int , int , int ,bool);

int main()
{
ifstream inData;
IntList values;
int item,fromLoc,toLoc,istep=0;
bool found = true;
char answer;

string msg = "Number out of range! ";
inData.open("int.dat");
do{
cout << fixed << showpoint;
cout << "Enter value to be searched for: "<< endl;
cin >> item;
cout << "Enter starting location in 0-9 range: "<< endl;
cin >> fromLoc;
cout << "Enter end location in 0-9 range: "<< endl;
cin >> toLoc;
try{
while(istep != MAX_LENGTH)
{
if((fromLoc <= 9) && (fromLoc >=0)&&(toLoc <= 9) &&
(toLoc >=0) && (fromLoc<toLoc))
{ cout << "Correct range! Do the search." <<endl;
BinarySearch(values,item,fromLoc,toLoc,found);
istep++;
cout << "This is the " << istep <<"th iteration,
do you want to continue? <Y/N> ";
cin >> answer;
if(answer == 'n')
{ cout << "Search abrted!";
cout << "There were " << istep << "
iterations.";
break;
}
}
else
throw msg;

}
}
catch(string message)
{
cout << message << "Search aborted!";

}
break;

}while(found = false);



cout << endl;
cout << "*******************************************************"
<< endl;

values.GetList(inData);
cout << "The list is : ";
values.PrintList();
cout << endl;
cout << "Length is " << values.LengthIs() << endl;
cout << "*******************************************************"
<< endl;
system("pause");
return 0;

}

IntList::IntList()
{
length =0;
}

void IntList::GetList(ifstream &data)
{
int value;

data >> value;

while(data)
{
for(int i=0;i<MAX_LENGTH;i++)
{
data >> value;
values = value;
length++;
}
cout << "List has been populated." << endl;
}

}

void IntList:rintList()
{
int index;
for(index=0;index<MAX_LENGTH;index++)
{
cout << values[index]<< " ";
}
}





int IntList::LengthIs()
{
return length;
}
bool BinarySearch(const IntList &values, int item, int first, int
last,bool found)
{

found = false;
int num = 1;
while(first <= last)
{
int mid = (first + last) / 2;

if(item > values[mid])
first = mid +1;
else if(item < values[mid])
last = mid - 1;
else

return found = true;
}

return found = false;
}

</code>

139 C: passing `const IntList' as `this' argument of `int
IntList:perator[](int)' discards qualifiers

 

[Ralph D. Ungermann]

I'm sorry guys; could anyone spell this out to me like I'm a ten year
old.

Ok, after I've started, I should continue...
(But you will find more help in alt.comp.lang.learn.c-c++)

class IntList
{
public:
IntList();
void GetList(ifstream &data);
void PrintList() const ;
int LengthIs() const ;
// int operator[](int mid) const ;
> // For the beginning, I'd recommend a normal function
> int get(int mid) const ;

I've added the `const' keyword to some functions, because they do not
modify the object. The advantage is, that you can invoke these methods
even for a const IntList.

bool BinarySearch(IntList *, int , int , int ,bool);

You forgot to change the type of the first argument to `const IntList
&', as you did in the definition below.



Don't forget the `const' keyword in the definitions:

void IntList:rintList() const

Also, you must define IntList::get():

int IntList::get(int i) const
{
return values;
}

bool BinarySearch(const IntList &values, int item, int first, int
last,bool found)
{ [...]
//later! if(item > values[mid])

if (item > values.get(mid))

139 C: passing `const IntList' as `this' argument of `int
IntList:perator[](int)' discards qualifiers

The message is clear:
- values is declared `const'
- operator[]() -- which I've replaced with get() -- was not defined for
const IntList objects.
With the modifications above, it should be fine now.


But again: BinarySearch() modifies only a local copy of `found'. Its
value in main() will not change!


Keep on!