Java字符串二分查找无法检索列表内目标关键字的问题排查
问题根因
- 二分查找的核心前置条件未满足:二分查找逻辑成立的前提是,待检索序列必须与比较规则匹配完成排序。当前代码使用
String.compareTo做大小判断,要求字符串数组必须提前按字典序升序排列,但代码中的books数组是完全乱序的。举个实际执行的例子:以当前key为"Rome"为例,数组长度为18,第一次计算mid = (0+17)/2 = 8,对应元素是"The survivor",该元素和"Rome"比字典序更大,程序直接把max设为7,后续所有检索范围都在索引0-7之间收缩,根本不会定位到索引0位置的"Rome",最终判定查找失败。 - 添加
"CCC"即可匹配的现象属于巧合:该元素的字典序位置比较特殊,当你把它放进数组列表时,其所在位置刚好落在单次执行流程计算出的初始mid检索范围内,直接触发匹配分支,并非搜索逻辑在乱序数组上实现了有效查找。 - 代码存在状态残留隐患:代码将
min、max、mid定义为类级别的静态变量,而非搜索方法内部的局部变量,后续多次调用搜索方法时,边界值会留存上一次调用的计算结果,哪怕修正了排序问题,多次检索也会出现异常的查找失败。
修正方案
- 搜索启动前,对字符串数组按字典序做升序排序,满足二分查找的前置要求
- 将搜索边界
min、max、mid调整为stringBinarySearch方法内部的局部变量,避免静态变量的状态残留
修正后可运行的代码示例:
import java.util.Arrays; static String[] books = { "Rome", "King Arthur", "The Johnson's", "Romeo and Juliet", "Hoodlums", "Baptist", "Rogue", "Marc Anthony", "The survivor", "Arc of Grace", "France", "Holy", "Mayor", "Fatality", "Immortal", "Fidelity", "The Major", "In the Hood" }; static String key = "Rome"; public static int stringBinarySearch() { int min = 0; int max = books.length - 1; int mid; while (min <= max) { mid = (min + max) / 2; if (books[mid].compareTo(key) < 0) { min = mid + 1; } else if (books[mid].compareTo(key) > 0) { max = mid - 1; } else { System.out.print("Book found and available at shelve "); return mid; } } System.out.println("Book not found"); return -1; } public static void main(String[] args) { Arrays.sort(books); System.out.println(stringBinarySearch()); }
内容的提问来源于stack exchange,提问作者Abubakar Oluyinka
相关产品推荐
相关产品推荐

