如何用二分查找判断单词是否存在于有序字母列表中

你的代码目前存在两个关键问题：一是没有处理中间元素不等于目标单词时的区间收缩逻辑，二是循环条件错误会导致死循环，同时索引初始化也不符合C#集合的0起始规则。

核心解决点：字符串的字典序比较 #

C#中可以直接使用string.Compare(string strA, string strB)方法按字母顺序比较字符串，返回值规则：

• 返回小于0：strA的字典序在strB之前（即strA更小）
• 返回等于0：两个字符串完全相等
• 返回大于0：strA的字典序在strB之后（即strA更大）

利用这个返回值，就能确定下一步要查找的半区：

• 如果中间元素比目标单词小（返回值<0），说明目标在右半区，把start设为mid + 1
• 如果中间元素比目标单词大（返回值>0），说明目标在左半区，把end设为mid - 1

修正后的完整代码 #

private static bool CheckWordIsValid(string targetWord, List<string> allowedWords)
{
    int start = 0; // C#集合索引从0开始，不是1
    int end = allowedWords.Count - 1;

    while (start <= end) // 循环条件：只要还有可查找的区间就继续
    {
        int mid = start + (end - start) / 2; // 避免start+end溢出的安全写法
        int compareResult = string.Compare(allowedWords[mid], targetWord, StringComparison.OrdinalIgnoreCase); // 可选忽略大小写，按需调整

        if (compareResult == 0)
        {
            // 找到目标单词，直接返回true
            return true;
        }
        else if (compareResult < 0)
        {
            // 中间单词比目标小，目标在右半区，收缩左边界
            start = mid + 1;
        }
        else
        {
            // 中间单词比目标大，目标在左半区，收缩右边界
            end = mid - 1;
        }
    }

    // 循环结束未找到目标，返回false
    return false;
}

代码说明 #

• 索引初始化：start设为0，end设为集合最后一个元素的索引（Count - 1），避免数组越界
• 循环条件：start <= end确保所有元素都被检查到，找不到目标时会正常退出循环
• 溢出安全的mid计算：start + (end - start)/2比(start+end)/2更安全，避免两个大整数相加溢出
• 大小写控制：如果你的单词列表不区分大小写，保留StringComparison.OrdinalIgnoreCase；如果需要严格区分，改用StringComparison.Ordinal（默认行为）

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