Binary Search

[dualdark]

I have a small problem with the binary search iterative, the algorithm is working good, but if i have more than one element with the same name, the program only shows one, i can't figure out what to do with the code in order to show every single element with the same name.

This is my code:

int Lista::Search(string element){
    int first=0,middle,last=tope;
    while(first<=last) {
        middle=(first+last)/2;
        if(element==data[middle].name){
            cout << "Position: " << mitad  << endl;
            data[middle].show();
            return data[middle].code;
        }
        if(element<data[middle].name){
            last=middle-1;
        }
        else {
            first=middle+1;
        }        
    }
    return -1;
}

Thanks in advance, any help is welcome =)

[coder777]

The problem in on line 8. What do you want to return if there's more than one?

Apart from that, if the array is sorted you need two loops to collect all elements:
The first loop is for the data on the left and the second for the names on the right.

[dualdark]

That's what I though, that I need two loops, but I don't k know where =S =(

[coder777]

Right before line 8. E.g. like so:

void Lista::Search(std::vector<int> &code_vector, string element){
    int first=0,middle,last=tope;
    while(first<=last) {
        middle=(first+last)/2;
        if(element==data[middle].name){
            cout << "Position: " << mitad  << endl;
            data[middle].show();

// Note
code_vector.push_back(data[middle].code);
for(int i = middle - 1; i >= 0; --i)
{
  if(data[i].name == data[middle].name)
    code_vector.push_back(data[i].code);
}
// Note: for(int j = middle + 1; j <= tope; ++j)
// ...
            break;
        }
        if(element<data[middle].name){
            last=middle-1;
        }
        else {
            first=middle+1;
        }        
    }
}

[dualdark]

oh tyvm.

One last thing tho, what is the "push_back" for?

[dhayden]

Don't you need to search forward also? Once you find an element that's equal, there could be more equal elements above or below it.

[dualdark]

ok got it ._. thanks a lot, it was very helpful