c++ - 带字符串数组的二进制搜索算法

Question

该程序应该在字符串数组中搜索名称。本来程序是适配int数据类型的，后来改成了string。我试图修改代码以使其运行并且确实如此，但我没有得到正确的输出。我的二进制搜索功能有问题。我的二进制搜索函数没有被正确编辑以适应数据类型从 int 到 string 的变化。它不会起作用，因为我在数组中有字符串而不是最初创建它的 int。其他一切似乎都正常工作。

这是我得到的输出。

Please enter an employee's name: Looney

That name does that exist in the array.

从技术上讲，我应该得到它存在的消息以及它的位置。

// This program demonstrates the binarySearch function, which
// performs a binary search on an integer array.

#include "stdafx.h"
#include <iostream>
#include <string> 
using namespace std;

// Function prototype
void sortArray(string [], int); 
int binarySearch(string [], int, string);
const int SIZE = 20;

int main()
{
    // Defined array 
    const int NUM_NAMES = 20;
    string names[NUM_NAMES] = {"Collins, Bill", "Smith, Bart", "Allen, Jim",
                               "Griffin, Jim", "Stamey, Marty", "Rose, Geri",
                               "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" };

    // Variables 
    string empName; 
    int results;  

    // Sort array first
    sortArray(names, NUM_NAMES); 

    // Prompt for user input to enter an employee name 
    cout << "Please enter an employee's name: "; 
    getline(cin, empName); 

    // Search for name
    results = binarySearch(names, NUM_NAMES, empName); 

    // If results contains -1 the name was not found.
    if (results == -1)
        cout << "That name does not exist in the array.\n";
    else
    {
        // Otherwise results contains the subscript of
        // the specified employee ID in the array.
        cout << "That name is found at element " << results;
        cout << " in the array.\n";
    }

    system("PAUSE"); 

    return 0;
}

//**************************************************************
// Definition of function sortArray.                           *
// This function performs an ascending order selection sort on *
// array. size is the number of elements in the array.         *
//**************************************************************
void sortArray(string names[], int size)
{
    int startScan, minIndex; 
    string minValue;

    for (startScan = 0; startScan < (size - 1); startScan++)
    {
        minIndex = startScan;
        minValue = names[startScan];
        for(int index = startScan + 1; index < size; index++)
        {
            if (names[index] < minValue)
            {
                minValue = names[index];
                minIndex = index;
            }
        }
        names[minIndex] = names[startScan];
        names[startScan] = minValue;
    }
}

//***************************************************************
// The binarySearch function performs a binary search on an     *
// integer array. array, which has a maximum of size elements,  *
// is searched for the number stored in value. If the number is *
// found, its array subscript is returned. Otherwise, -1 is     *
// returned indicating the value was not in the array.          *
//***************************************************************
int binarySearch(string names[], int size, string value)
{
    int first = 0,             // First array element
        last = size - 1,       // Last array element
        middle,                // Mid point of search
        position = -1;         // Position of search value
    bool found = false;        // Flag

    while (!found && first <= last)
    {
        middle = (first + last) / 2;     // Calculate mid point
        if (names[middle] == value)      // If value is found at mid
        {
            found = true;
            position = middle;
        }
        else if (names[middle] > value)  // If value is in lower half
            last = middle - 1;
        else
            first = middle + 1;           // If value is in upper half
    }
    return position;
}

Answer 1

因为名称 Looney 不存在于数组中。

您应该输入 Looney, Joe 以获得预期的输出。

输入错误，否则您的实现看起来不错。