字符串数组的二分查找工作原理及代码中字符串比较逻辑解析

Hey there! Let's tackle your questions about binary search with string arrays, starting with your core confusion about how array[mid] < value works, then fixing a few bugs in your code that might be tripping you up.

How does array[mid] < value work for strings in C++? #

In C++, the std::string class overloads the < operator to compare strings using lexicographical order—think of how words are sorted in a dictionary. Here's the exact logic:

• It compares characters one by one from the start of each string, using their ASCII values.
• The first pair of differing characters determines the result: if the character in array[mid] has a lower ASCII value than the corresponding character in value, then array[mid] < value is true.
• If all compared characters are identical, the shorter string is considered "less than" the longer one. For example, "apple" < "apples" evaluates to true.

Let's use your array as an example: if array[mid] is "ciku" and value is "durian", the first character 'c' (ASCII 99) is less than 'd' (ASCII 100), so "ciku" < "durian" is true, and we adjust low to mid + 1 to search the right half of the array.

Fixing Bugs in Your Code #

Your binary search has a few issues that will prevent it from working correctly—let's fix them:

1. Incorrect while loop condition: while(low<=low) is a typo; it should be while(low <= high) to keep searching as long as the search range is valid.
2. Out-of-bounds array access: Your array has 5 elements (indices 0-4), but you initialized high = 5—this will cause array[5] to access memory outside the array. Set high = 4 instead.
3. Mismatched output message: You're searching for "banana" but printing "Location of durian"—this is just a confusing typo.

Here's the corrected code:

#include <iostream>
#include <string> // Use <string> instead of <string.h> for std::string
using namespace std;

int linearSearch(string array[], string value);
int binarySearch(string array[], string value);

int main(int argc, const char * argv[]) {
    string array[] = {"apple","banana","ciku","durian","rambutan"};
    string value = "banana";
    
    // Linear search
    int location = linearSearch(array, value);
    cout << "Location of " << value << " (linear search): " << location << endl;
    
    // Binary search
    int position = binarySearch(array, value);
    cout << "Location of " << value << " (binary search): " << position << endl;
}

int binarySearch(string array[], string value){
    int low = 0;
    int high = 4; // Fixed: array indices are 0-4
    while(low <= high){ // Fixed: correct loop condition
        int mid = (low + high) / 2;
        if(array[mid] == value){
            return mid;
        }
        else if (array[mid] < value){
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }
    return -1; // Return -1 if value not found
}

int linearSearch(string array[], string value){
    int arrayLength = 5;
    for(int i=0; i<arrayLength; i++){
        if(array[i] == value){
            return i;
        }
    }
    return -1;
}

Quick Recap of Binary Search for String Arrays #

Binary search works on sorted arrays (your string array is already sorted lexicographically, which is perfect). Here's the step-by-step for your example:

1. Start with low = 0 and high = 4.
2. Calculate mid = (0+4)/2 = 2 (element "ciku").
3. Compare "ciku" with "banana": since "ciku" > "banana" (lex order), set high = 2-1 = 1.
4. Now low=0, high=1: calculate mid=(0+1)/2=0 (element "apple").
5. "apple" < "banana", so set low=0+1=1.
6. Now low=1, high=1: mid=1 (element "banana"), which matches the value—return index 1.

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