使用字符串數組而不是int數組實現二分搜索

Question

該程序應該將其納入其中。我創建了大部分代碼，但這是我實驗室的第二部分，我必須返回並輸入二進制搜索的字符串。我不知道如何搜索字符串，如果我必須刪除idNum和結果以及empId。

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" }; 

因此，二分查找將使用字符串而不是int。我不明白該怎麼做。

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

    int main() 
    { 

     // Array with employee IDs sorted in ascending order. 
     int idNums[SIZE] = {101, 142, 147, 189, 199, 207, 222, 
          234, 289, 296, 310, 319, 388, 394, 
          417, 429, 447, 521, 536, 600}; 
     int results; // To hold the search results 
     int empID;  // To hold an employee ID 

     // Get an employee ID to search for. 
     cout << "Enter the employee ID you wish to search for: "; 
     cin >> empID; 

     // Search for the ID. 
     results = binarySearch(idNums, SIZE, empID); 

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

binarySearch函數對整數數組執行二分搜索。具有最大尺寸元素的數組，搜索存儲在數值中的數字。如果找到該數字，則返回其數組下標。否則，返回-1，表示該值不在數組中。

int binarySearch(const int array[], int size, int 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 (array[middle] == value)  // If value is found at mid 
     { 
     found = true; 
     position = middle; 
     } 
     else if (array[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

變化

int binarySearch(const int array[], int size, int value) 

到

int binarySearch(const std::string array[], int size, const std::string &value) 

，然後用它如下

std::string name; 
std::getline(std::cin, name); // read name from console 
std::sort(names, names + NUM_NAMES); // make sure the array is sorted 
results = binarySearch(names, NUM_NAMES, name); 

你也可以利用模板，這樣你的代碼是比較通用的

template<typename T> 
int binarySearch(const T array[], int size, const T &value)