Java中如何通过二分查找提取两个ArrayList所有匹配索引对应字符串

你当前代码的几个关键错误 #

• Collections.binarySearch参数用错了：这个方法的设计是，第一个参数传已经升序排好的待搜列表，第二个参数传单个要找的目标值，你现在把整个bList当目标值传进去，哪怕能编译过，找出来的结果也完全不对——本质是在aList里找哪个元素能等于整个bList对象，基本不可能命中。
• 字符串比较方式错了：Java里比字符串内容必须用equals()，!=和==比的是对象的内存地址，不是内容，写出来的判断逻辑根本不准。
• 找左边界的循环逻辑完全不对：循环里执行一次--index就直接break，最多往左跳一步，根本没法走到连续匹配串的最左边；而且你连边界判断都没加，如果匹配位置在列表开头，访问index-1直接数组越界报错。
• 对二分查找的前提认知不对：二分查找要求待搜列表必须提前排序，这种情况下所有和目标字符串相等的元素一定是连续挤在一起的，不会零散分布，根本不用逐个从头扫所有匹配项，只要找到这堆连续元素的头和尾，中间的全是匹配的。

可直接落地的实现步骤 #

1. 先确认你要搜索的那个列表，已经按字符串升序排完了，不然二分查找的结果完全是随机的，不可信。
2. 把binarySearch的调用改对：传单个待匹配的目标字符串进去，拿到一个随便哪个匹配位置就行（只要返回值>=0就说明有匹配项）。
3. 从这个随机的匹配位置开始，往左走定位连续匹配段的最左端：只要当前位置的前一个元素和目标值相等，就继续往左挪，同时要保证索引不能小于0，直到遇到第一个不相等的元素，或者走到列表开头，停住的位置就是第一个匹配项的索引。
4. 再从随机匹配位置开始，往右走定位连续匹配段的最右端：只要当前位置的后一个元素和目标值相等，就继续往右挪，同时要保证索引不超出列表范围，直到遇到第一个不相等的元素，或者走到列表末尾，停住的位置就是最后一个匹配项的索引。
5. 把左边界到右边界这一段的所有字符串取出来，就是全部的匹配结果。

可直接参考的代码示例 #

// 待搜索的已排序字符串列表
List<String> sortedList = new ArrayList<>(List.of("apple", "banana", "banana", "banana", "orange", "orange"));
// 待匹配的目标字符串
String target = "banana";

// 二分查找拿到任意一个匹配位置
int midIndex = Collections.binarySearch(sortedList, target);
List<String> matchedResult = new ArrayList<>();

if (midIndex >= 0) {
    // 往左找左边界
    int leftBound = midIndex;
    while (leftBound > 0 && sortedList.get(leftBound - 1).equals(target)) {
        leftBound--;
    }

    // 往右找右边界
    int rightBound = midIndex;
    int listSize = sortedList.size();
    while (rightBound < listSize - 1 && sortedList.get(rightBound + 1).equals(target)) {
        rightBound++;
    }

    // 收集区间内所有匹配字符串
    for (int i = leftBound; i <= rightBound; i++) {
        matchedResult.add(sortedList.get(i));
    }
}

特殊场景提醒 #

如果待搜索的列表根本没排序，那二分查找完全用不了，这时候只能写个普通for循环从头到尾扫一遍，遇到匹配的就收集索引和对应字符串就行。但如果列表数据量比较大，优先选「先排序、再用二分法定位边界」的方案，效率比全表遍历高很多。

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