字符串向量二分查找

Question

我正在尝试使用二分搜索在字符串向量中查找用户输入的单词。但它总是返回一个正整数。 对向量进行排序并从 txt 文件中读取。 该文件看起来像。

aah
aal
aas

等等。

    int binarySearchString(vector<string> arr, string x, int n) {
    int lower = 0;
    int upper = n - 1;
    while (lower <= upper) {
    int mid = lower + (upper - lower) / 2;
    int res;
    if (x == (arr[mid]))
     res = 0;
    if (res == 0)
     return mid;
    if (x > (arr[mid]))
      lower = mid + 1;
    else
     upper = mid - 1;
    }
    return -1;
    }

Answer 1

事实上，除非 x == (arr[mid]) 为 true，否则这段代码应该抛出运行时异常，因为 res 将在下一个 if 语句中使用。已初始化。当我将 res 初始化为某个负值时，该函数似乎可以工作。

int binarySearchString(vector<string> arr, string x, int n) {
    int lower = 0;
    int upper = n - 1;
    while (lower <= upper) {
        int mid = lower + (upper - lower) / 2;
        int res = -2;

        if (x == (arr[mid]))
            res = 0;

        if (res == 0)
            return mid;

        if (x > (arr[mid]))
            lower = mid + 1;
        else
            upper = mid - 1;
    }
    return -1;
}

使用 binarySearchString(words, "bbb", 3); 调用它会返回 -1。

int main()
{
    vector<string> words;
    words.push_back("aah");
    words.push_back("aal");
    words.push_back("aas");

    int retVal = binarySearchString(words, "bbb", 3);

    std::cout << "Returned: " << retVal << std::endl;

    system("pause");
    return 0;
}