Java字符串数组二分查找实现失败，求错误排查与正确方案

当然可以，但二分查找的核心前提是数组必须是有序的，同时你的代码存在几个关键错误，导致查找失败：

你的代码错误分析 #

1. 数组未排序
   二分查找只能在有序集合中生效，你的数组{"Dossa" , "Maggie" , "Chai" , "Coffe"}是无序的，这是查找失败的根本原因。

2. 字符串比较方式错误
   Java中==用于比较对象的引用地址，而非字符串内容。要比较字符串值是否相等，应该用a[mid].equals(key)，或者用compareTo()方法判断大小关系（用于二分查找的逻辑分支）。

3. 二分查找逻辑错误
   你的循环中每次同时执行start++和end--，完全偏离了二分查找的核心逻辑——通过比较中间元素与目标值的大小，将查找范围缩小一半：

   • 如果中间元素小于目标值，应将start设为mid + 1（去右半部分查找）
   • 如果中间元素大于目标值，应将end设为mid - 1（去左半部分查找）

修正后的代码实现 #

先对数组排序，再修正比较和查找逻辑：

import java.util.Arrays;

public class BinarySearchString {
    public static void main(String[] args) {
        String a[] = {"Dossa" , "Maggie" , "Chai" , "Coffe"};
        // 先对数组进行排序
        Arrays.sort(a);
        String key = "Coffe";
        int index = hwq(a , key);
        if(index == -1 ){
            System.out.print("NOT FOUND ");
        }else{
            System.out.print(key + " is at index = " + index);
        }
    }

    public static int hwq(String a[] , String key){
        int start = 0 , end = a.length - 1;
        while(start <= end){
            int mid = start + (end - start) / 2; // 避免start+end溢出
            // 用compareTo比较字符串大小，返回值：负=小于，0=等于，正=大于
            int compareResult = a[mid].compareTo(key);
            if(compareResult == 0){
                return mid ;
            } else if(compareResult < 0){
                // 中间元素小于目标，去右半部分找
                start = mid + 1;
            } else {
                // 中间元素大于目标，去左半部分找
                end = mid - 1;
            }
        }
        return -1;
    }
}

其他解决方案 #

直接使用Java标准库提供的Arrays.binarySearch()方法，它已封装正确的二分查找逻辑，支持字符串数组（前提是数组已排序）：

import java.util.Arrays;

public class BinarySearchString {
    public static void main(String[] args) {
        String a[] = {"Dossa" , "Maggie" , "Chai" , "Coffe"};
        Arrays.sort(a);
        String key = "Coffe";
        int index = Arrays.binarySearch(a, key);
        if(index < 0 ){
            System.out.print("NOT FOUND ");
        }else{
            System.out.print(key + " is at index = " + index);
        }
    }
}

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