Поиск массива строк

В вашей функции search() конструкция do { } while; { } ошибочна. Он скомпилируется, но не будет делать то, что вы хотите. Я внес несколько изменений и изменил ваш код, чтобы он имел больше смысла.

void search(string *array, int size)
{
    string name;

    for (;;)
    {
        cout<<"Please enter a name or END to terminate:";
        getline(cin, name);
        if (name == "END") break;

        int first = 0;
        int last = size - 1;
        bool friends = false;

        while (!friends && first <= last)
        {
            int middle = (first + last) / 2;
            if (array[middle] == name)
            {
                friends = true;
                cout<<array[middle]<<" is my friend."<<endl;
            }
            else if (array[middle] > name)
                last = middle - 1;
            else
                first = middle + 1;
        }
    }
}

int main () // test the search() function
{
    string array[] = { "bird", "cat", "dog", "horse", "loon", "zebra" };
    search(array, 6);
}

ТАК, это слишком много домашней работы? Должен ли я удалить это?

Мне кажется интересным, что вы установили last в оба случаях, когда не нашли соответствия.

Первое, что вы должны сделать, это подумать о том, что это значит, подтолкнуть, подтолкнуть, подмигнуть, подмигнуть :-)

Вы также должны передать количество используемых элементов в search, а не размер массива (поскольку вы можете использовать не весь массив).

Я полагаю, что

search(friendArray, maxsize);

должно быть

search(friendArray, sub);

Входное условие бинарного поиска состоит в том, что искомый массив отсортирован. Ваш массив выглядит так:

Aaron Burr
Bill Cosby
Celine Dion
...
Zachary Taylor
""
""
""
""

etc.

Так как пустая строка не меньше непустой строки, то friendArray[0..maxsize] не сортируется, а массив friendArray[0..sub] сортируется.

Оператор >> читает отформатированные данные из потока, т.е. отбрасывает пробелы. Когда вы произносите cin >> name; и вводите «Элвис Пресли», в name сохраняется только «Элвис».

Вам нужно getline(cin, name);

Подумайте, что произойдет, если длина вашего массива friends будет равна 3. Если не ошибаюсь, будет проблема.

Также рекомендуется использовать более безопасные типы данных, такие как vector<string>, например, тогда вам не нужно заботиться о слишком большом количестве данных во входном файле. Также ваша жизнь станет проще в функции поиска, так как вы можете использовать итераторы и не нужно передавать размер массива.

Посмотрите, что люди говорят в других ответах о cin.

Это одна петля do-whi:

do
{
 cout<<"Please enter a name or END to terminate:";
 cin>>name;
}
while(!friends && first <= last && name != "END");

Код будет в основном зацикливаться навсегда (друзья никогда не будут истинными, а первый никогда не будет> последним), запрашивая у вас имя, пока вы либо не завершите программу, либо не наберете «КОНЕЦ».

Этот:

{
    middle = (first + last) / 2;
    if (array[middle] == name)
        {
            friends = true;
            cout<<array[middle]<<" is my friend."<<endl;
        }
    else if (array[middle] > name)
        last = middle - 1;
    else
        last = middle + 1; 
}

не будет возможности выполниться, пока условие цикла не станет ложным (в данном случае, пока вы не наберете «КОНЕЦ»).

Вы говорите, что вроде все работает, за исключением случаев, когда вы ввели имя для поиска. На самом деле, вы попали в точку. В вашем двоичном коде поиска ошибка. И первый ответ в этой теме в сторону этого пути.

Если массив используется в бинарном поиске, он должен быть разбит на две части на каждом этапе поиска.

Например, на этапе, если текущая часть отмечена следующим образом: первая - средняя - последняя, ​​на следующем этапе части будут либо между первой - средней - 1, либо средней + 1 - последней.

So

    else if (array[middle] > name)
      last = middle - 1;
    else 
      last = middle + 1;

должно быть

  else if (array[middle] > name)
      last = middle - 1;
  else 
      first = middle + 1;

У вас есть ошибка на единицу в вашей сортировке.

Проблема в поиске функций. переместите } после cin>>name в конец функции, чтобы она выглядела так:

void search(string *array, int size)
{
    int first = 0;
    int last = size - 1;
    int middle;
    string name;
    bool friends = false;

    do
    {
        cout<<"Please enter a name or END to terminate:";
        cin>>name;

        while(!friends && first <= last && name != "END");
        {
            middle = (first + last) / 2;
            if (array[middle] == name)
            {
                friends = true;
                cout<<array[middle]<<" is my friend."<<endl;
            }
            else if (array[middle] > name)
                last = middle - 1;
            else 
                last = middle + 1;
        }
    }
}