What is wrong with my binary search?

[Meden]

// Binary String Search.
// This program uses the data from BE0804 to conduct a binary search.

#include <iostream>
#include <cstring>
using namespace std;

int main(){
    const int M = 17;
    char names[20][M] = {"Collins, Bill",
                          "Smith, Bart",
                          "Allen, Jim",
                          "Griffin, Jim",
                          "Stamey, Marty",
                          "Rose, Gerti",
                          "Taylor, Terri",
                          "Johnson, Jill",
                          "Allison, Jeff",
                          "Looney, Joe",
                          "Wolfe, Bill",
                          "James, Jean",
                          "Weaver, Jim",
                          "Pore, Bob",
                          "Rutherford, Greg",
                          "Javens, Renee",
                          "Harrison, Rose",
                          "Setzer, Cathy",
                          "Pike, Gordon",
                          "Holland, Beth"};
    int n1, n2, pos;
    char NameHolder[M], UserEntry[M];
    int first = 0, last = M, middle;
    bool found = false, stop = false;
    int enter[M];

    for (n1 = 0; n1 < M-1; n1++){
        strcpy(NameHolder, names[n1]);
        pos = n1;
        for (n2 = n1 + 1; n2 < M; n2++){
            if (int(names[n2][0]) < int(NameHolder[0])){
                strcpy(NameHolder, names[n2]);
                pos = n2;
            }
        }
        strcpy(names[pos], names[n1]);
        strcpy(names[n1], NameHolder);
    }
    cout << "Alphabetical names." << endl << endl;
    for (n1 = 0; n1 < M; n1++){
        cout << names[n1] << endl;
    }
    cout << "Enter a name to search for.  The form must be Last, First." << endl;
    cin >> UserEntry;
    cout << endl;

    while (!found && first <= last){    // While found is false and first is less than last
        middle = (first + last) / 2;    // middle is set to a value between first and last
        if (UserEntry == names[middle]){    // if UserEntry is the selected middle name of the list
            found = true;   // then found is true.  This should break the while.
        }
        else{   // Otherwise if UserEntry is not the selected middle name...
            for (n1 = 0; stop == false; n1++){    // Enter a new loop that sets n1 = 0 and repeats until stop = true.  n1++ every iteration.
                middle = (first + last) / 2;  // For the sake of the new loop, middle is set again to be between first and last.
                if (int(names[middle][n1]) < int(UserEntry[n1])){   // If the int value of the n1'th letter, 
                                                                    // starting with 0 is less than the int value of UserEntry[n1]
                    first = middle + 1; // The first name in the search range becomes the name one above middle.
                    stop = true;    // and the stop flag is set to true, thus breaking the for loop.
                }
                if (int(names[middle][n1]) > int(UserEntry[n1])){  // If the same condition is instead greater than
                    last = middle - 1; // The last name in the search range becomes the name one below middle.
                    stop = true;    // and the stop flag is set to true.
                }   // If neither condition is true, it must be assumed that: 
                    // 1. the user entry does not match the middle selection, 
                    // and 2. the n1'th letters of both do match, thus the loop
                    // just needs to move on to n1++.
            }
        }

    }
    if (found == true)
        cout << "That name exists." << endl;
    else
        cout << "Invalid entry." << endl;


}

I've gone through the code again and again, and I just can't see what is wrong with it. What happens is that it loops forever, but besides that it seems that found is never true.

[domaa]

I'm new to programing and don't really know what i'm doing. So really just looking at a lot of code. One thing i noticed is in line 62.

for (n1 = 0; stop == false; n1++){

// Enter a new loop that sets n1 = 0 and repeats until stop = true. n1++ every iteration.

your notes say repeats until stop but your code says stop == false as the end case for the for loop.

I think i'm reading that right.

[coder777]

line 56: while (!found && first < last){ // While found is false and first is less than last

comare the strings with strcmp:

http://www.cplusplus.com/reference/clibrary/cstring/strcmp/

On line 58 you compare pointers which are never the same.
within the else branch you don't need the loop. strcmp() does it for you

[Meden]

Thanks for the strcmp suggestion. I forgot about it. I haven't yet learned enough about pointers. What do you mean "On line 58 you compare pointers which are never the same." I have rewritten the while area which conducts the search. I have tested the variable middle with a cout, and it seems to be working fine. The only problem left is that strcmp(names[middle], UserEntry) is never true, or zero anyway, and I do not yet know why.

    while (found == false && first <= last){
        middle = (first + last) / 2;
        if (strcmp(names[middle], UserEntry) == 0)
            found = true;
        else if (strcmp(names[middle], UserEntry) > 0)
            last = middle -1;
        else
            first = middle +1;
        cout << middle << endl;
    }

[coder777]

The only problem left is that strcmp(names[middle], UserEntry) is never true, and I do not yet know why.

The problem is on line 53: cin >> UserEntry;

>> stops at the first space. i.e. if you enter "Allison, Jeff" UserEntry contains "Allison,"

use getline() for that:

http://www.cplusplus.com/reference/iostream/istream/getline/

What do you mean "On line 58 you compare pointers which are never the same."

No matter if you learned about pointer or not you did compare the pointer

[Meden]

Thank you.