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(ifstrea m &data);
void PrintList();
int LengthIs();
private:

int length;
int values[MAX_LENGTH];
};

bool BinarySearch(In tList [], int , int , int ,bool);

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

string msg = "Number out of range! ";
inData.open("in t.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(in fo,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(in Data);
cout << "The list is : ";
info.PrintList( );
cout << endl;
cout << "Length is " << info.LengthIs() << endl;
cout << "************** *************** *************** ***********"
<< endl;
system("pause") ;
return 0;

}

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

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

data >value;

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

}

void IntList::PrintL ist()
{
int index;
for(index=0;ind ex<MAX_LENGTH;i ndex++)
{
cout << values[index]<< " ";
}
}

int IntList::Length Is()
{
return length;
}

bool BinarySearch(In tList 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(In tList*, int, int, int, bool)'
D:\ In function `bool BinarySearch(In tList*, int, int, int, bool)':
137 D:\
no match for 'operator>' in 'item *((+(((unsigned int)mid) * 44u)) +
info)'

[Victor Bazarov]

zf*****@mail.co m wrote:

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

bool BinarySearch(In tList [], 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(In tList*, 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(in fo,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(In tList*, int, int, int, bool)'

Right. See above for the correction.

D:\ In function `bool BinarySearch(In tList*, 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[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(In tList &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(In tList *, int , int , int ,bool);//prototype
Please help
BinarySearch(&i nfo,item,fromLo c,toLoc,found); // function being called
in main
</code>

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

[Victor Bazarov]

zf*****@mail.co m wrote:

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(In tList &info, int item, int first, int last,bool

<sigh So, you changed the first argument to be a reference?

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(In tList *, int , int , int ,bool);//prototype

Your prototype does not match the definition.

>

Please help
BinarySearch(&i nfo,item,fromLo c,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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Ralph D. Ungermann]

zf*****@mail.co m wrote:

class IntList
{
public:
IntList();
void GetList(ifstrea m &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(In tList info[], int item, int first, int last,bool
found)
{

[snipped]

if(item info[mid])

D:\ In function `bool BinarySearch(In tList*, 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[i]" 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(m id)" 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(ifstrea m &data);
void PrintList();
int LengthIs();
int operator[](int mid);
private:

int length;
int values[MAX_LENGTH];
};

bool BinarySearch(In tList *, int , int , int ,bool);

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

string msg = "Number out of range! ";
inData.open("in t.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(va lues,item,fromL oc,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.PrintLis t();
cout << endl;
cout << "Length is " << values.LengthIs () << endl;
cout << "************** *************** *************** ***********"
<< endl;
system("pause") ;
return 0;

}

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

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

data >value;

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

}

void IntList::PrintL ist()
{
int index;
for(index=0;ind ex<MAX_LENGTH;i ndex++)
{
cout << values[index]<< " ";
}
}

int IntList::Length Is()
{
return length;
}
bool BinarySearch(co nst 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::operat or[](int)' discards qualifiers

[Ralph D. Ungermann]

zf*****@mail.co m wrote:

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.l earn.c-c++)

class IntList
{
public:
IntList();
void GetList(ifstrea m &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(In tList *, 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::PrintL ist() const

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

int IntList::get(in t i) const
{
return values[i];
}

bool BinarySearch(co nst 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::operat or[](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!