C++员工姓名搜索：迭代式二分查找代码补全技术问询

First, an important note: binary search only works correctly on sorted arrays. The name array you provided isn't sorted lexicographically, so I've sorted it first (otherwise the search won't return accurate results). Here's the sorted version of your array with setup code:

#include <iostream>
#include <string>
#include <algorithm> // For std::sort to sort the array

using namespace std;

const int size = 20;
string name[size] = {"Collins, Bill", "Smith, Bart", "Michalski, Joe", "Griffin, Jim", "Sanchez, Manny", 
                     "Rubin, Sarah", "Taylor, Tyrone", "Johnson, Jill", "Allison, Jeff", "Moreno, Juan", 
                     "Wolfe, Bill", "Whitman, Jean", "Moretti, Bella", "Wu, Hong", "Patel, Renee", 
                     "Harrison, Rose", "Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth"};

Now, here's the complete iterative binary search function, with clear explanations:

int binarySearchIterative(string name[], int size, string empName) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        // Calculate mid safely to avoid integer overflow (better than (low + high)/2)
        int mid = low + (high - low) / 2;

        if (name[mid] == empName) {
            // Found the employee, return their index
            return mid;
        } else if (name[mid] < empName) {
            // Target name is lex larger, search the right half
            low = mid + 1;
        } else {
            // Target name is lex smaller, search the left half
            high = mid - 1;
        }
    }

    // If loop exits without returning, the name wasn't found
    return -1;
}

Key Details: #

• Safe Mid Calculation: Using low + (high - low)/2 instead of (low + high)/2 prevents integer overflow when working with large array sizes (a good habit even if not needed here).
• String Comparisons: std::string overloads comparison operators (<, ==, etc.) to work lexicographically, which is exactly what we need for name sorting and searching.
• Return Values: The function returns the index of the matching name if found, or -1 if the name isn't present in the array.

Example Test Code: #

Add this to your main function to verify the search works:

int main() {
    // Sort the array first (required for binary search)
    sort(name, name + size);

    // Test searching for a valid name
    string searchName = "Smith, Cathy";
    int result = binarySearchIterative(name, size, searchName);

    if (result != -1) {
        cout << "Found " << searchName << " at index " << result << endl;
    } else {
        cout << searchName << " not found in the array." << endl;
    }

    // Test searching for an invalid name
    searchName = "Doe, John";
    result = binarySearchIterative(name, size, searchName);

    if (result != -1) {
        cout << "Found " << searchName << " at index " << result << endl;
    } else {
        cout << searchName << " not found in the array." << endl;
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者user9468830