字符串向量二分查找

Question

我正在尝试使用二进制搜索在字符串向量中查找用户输入的单词。但它总是 returns 一个正整数。对矢量进行排序并从 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]) 为真，否则此代码应抛出运行时异常，因为 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); returns -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;
}

字符串向量二分查找

String vector binary search

c++

string

algorithm

vector

binary-search