Search code examples
c++stringalgorithmvectorbinary-search

String vector binary search


I am trying to find a user input word inside a string vector using binary search. But it always returns a positive integer. The vector is sorted and read from a txt file. The file looks like.

aah
aal
aas

and so on.

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

Solution

  • As it is, unless x == (arr[mid]) is true, this code should throw a runtime exception because res will be used in the next if statement before it's been initialized. When I initialize res to some negative value, the function seems to work.

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

    Calling it with 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;
    }