Hello people, I know how simple binary search works, but how can I do a double binary search, we got students each with a name and a code, I need in my binary search to find a student by name AND by code, using ONLY binary search.How could I do that ???
Please, I don't see how to express the binary search algorithm that is going to exclude another student, with the same name, but a different code.
It's in C++, just the idea.

## All 8 Replies

The comparisons are not limited to just one field within a class or structure, you can compare as many class objects such as strings that you want to. In the comparison, if the two names being compared are the same then compare the code.

Instead of me guessing, what is it that you are trying to search? An array of structures or classes, a linked list, or what ?

Ok I'll post the code.

lets say you have an array of structures

``````struct Students
{
std::string name;
int studenID;
};

Students stdarray;``````

Now you want to find the row for "Smith" code 123; Here is how the comparison function should work

``````int compare(Student* s1, Student* s2)
{
int rtn = s1->name.compare(s2->name);
if(rtn == 0)
{
rtn = s1->code - s2->code;
}
return rtn;
}``````

}

``````struct student{
string name;
char code;
};

void typing(int &N,struct student vector[]);
void sorting_pr_name_et_code(int N,struct student vector[]);
void find_element(int &N,struct student vector[]);

void typing(int &NS,struct student vector[])
{
int i,j;
cout<<"How many students ?"<<endl;
cin>>NS;
for(j=0;j<NS;j++){cout<<"Nameofstudent "<<i+1<<endl;
cin>>vector[i].name;
}
for(j=0;j<NS;j++){

cout<<"code student"<<i+1<<endl;
cin>>vector[i].code;}
}

void sorting_pr_name_et_code(int N,struct student vector[])
{ int i;
bool permutation;
struct student temp;

do{
permutation=false;
for(i=0;i<N-1;i++){
if(vector[i].name<vector[i+1].nom){}else{if(vector[i].name>vector[i+1].name)
{
temp=vector[i];
vector[i]=vector[i+1];
vector[i+1]=temp;
permutation=true;}else{
if(vector[i].code<vector[i+1].code){}else{
temp1=vector[i];
tableau[i]=tableau[i+1];
tableau[i+1]=temp1;
permutation=true;
}
}
}
}
}while(permutation==true);
}

void find_element(int &N,struct student vector[]){
int Left=0,Right=N-1,M,i,NC=0;
string element;
char code;
bool found=false;

cout<<"What's the name of the element ?"<<endl;
cin>>element;
cout<<"What's the code of the element"<<endl;
cin>>code;
//binary search
while((Left<=Right)&&(found==false)){
M=((Left+Right)/2);

if((element==vector[M].nom)&&(code==vector[M].code){
cout<<"element  found"<<endl;
cout<<"The index is "<<M<<endl;
found=true;
}else{
if(element<vector[M].name){Right=M-1;}else{Left=M+1;}
}
}

How can I find an element by name AND code using ONLY binary search???
I'm desperate.

void main (){
const int Nmax=12;
int N;
struct student vector[Nmax];

typing(N,vector);
sorting_pr_name_et_code(N,vector);
find_element(N,vector);

}``````

Please use code tags. It makes your code much more readable. What are the criteria for whether one student is less than another? You need to write a comparison function:

``````int StudentCompare(student student1, student student2)
{
// return -1 if student1 is less than student2
// return 0 if student1 == student2
// return 1 if student1 is greater than student2
}``````

You'll need to define "less than", "equal", and "greater than" based on your criteria, whatever they are. Ancient Dragon laid out some good criteria for the comparison, but make sure it's the same criteria as you have before implementing. So when you need to decide where to go in your array to search, call this function to compare two students and make your decision based on its results. It's similar to the compare function from the string class except you need to write it yourself.

I don't see how to express the binary search algorithm that is going to exclude another student, with the same name, but a different code.

So can two student have the same name with a different code? Is that legal? What does "exclude" mean here?

I tried compiling the code but I think some of it is written in french? O_o

comply: there were a few translation problems but I managed to fix them so that I could show you what you need to do.

First, I added a comparison method in that structor that returns an integer similar to strcmp() or std::string's compare()

``````struct student
{
string name;
char code;
int operator==(struct student& st)
{
int ret = name.compare(st.name);
if(ret == 0)
{
ret = code - st.code;
}
return ret;

}
};``````

Here is a partially rewritten find function. You still have to finish it to update the new value of M if the structure comparison is not 0.

``````void find_element(int &N,struct student vector[])
{
int Left=0,Right=N-1,M,i,NC=0;
string element;
char code;
bool found=false;

cout<<"What's the name of the element ?"<<endl;
cin>>element;
cout<<"What's the code of the element"<<endl;
cin>>code;
//binary search
struct student st;
st.name = element;
st.code = code;
while((Left<=Right)&&(found==false))
{
M=((Left+Right)/2);
int cmp = (vector[M] == st);
if(cmp == 0)
{
cout<<"element  found"<<endl;
cout<<"The index is "<<M<<endl;
found=true;
}
// Add code here to compute new value of Left or Right.
}
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.