Java 二分查找插入實作：Comparable 介面與有序集合維護

應用場景

維護一個按 sessionId 排序的集合，需快速判斷是否存在、不存在則插入、存在則計數 +1。二分查找將查詢/插入從 O(n) 降為 O(log n)。

資料模型 Bean

package uv;

public class Bean implements Comparable<Bean> {
    private String sessionId;
    private Integer num = 1;

    public Bean(String sessionId) { this.sessionId = sessionId; }
    public String getSessionId() { return sessionId; }
    public void setSessionId(String sessionId) { this.sessionId = sessionId; }
    public Integer getNum() { return num; }
    public void setNum(Integer num) { this.num = num; }
    public void increase() { ++num; }

    @Override
    public int compareTo(Bean o) {
        return this.sessionId.compareTo(o.getSessionId()); // 按 sessionId 自然序
    }

    @Override
    public String toString() { return sessionId; }
}

二分查找插入核心邏輯

import java.util.ArrayList;
import java.util.List;

public class BinarySearchInsert {
    private final List<Bean> list = new ArrayList<>();

    /** 查找索引：存在回傳索引，不存在回傳 -(插入點) - 1 */
    private int binarySearch(String sessionId) {
        int lo = 0, hi = list.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            int cmp = list.get(mid).getSessionId().compareTo(sessionId);
            if (cmp < 0) lo = mid + 1;
            else if (cmp > 0) hi = mid - 1;
            else return mid; // 找到
        }
        return -lo - 1; // 未找到，lo 為插入點
    }

    /** 插入或計數 +1 */
    public void addOrIncrement(String sessionId) {
        int idx = binarySearch(sessionId);
        if (idx >= 0) {
            list.get(idx).increase();
        } else {
            int insertPos = -idx - 1;
            list.add(insertPos, new Bean(sessionId));
        }
    }

    public List<Bean> getList() { return list; }

    public static void main(String[] args) {
        BinarySearchInsert bsi = new BinarySearchInsert();
        bsi.addOrIncrement("s3");
        bsi.addOrIncrement("s1");
        bsi.addOrIncrement("s2");
        bsi.addOrIncrement("s1"); // 重複
        bsi.getList().forEach(System.out::println);
        // 輸出: s1, s2, s3 (s1.num=2)
    }
}

關鍵點總結

生產級替代方案

• TreeMap<String, Integer>：紅黑樹，自動排序、O(log n) 查找/插入、API 簡單
• ConcurrentSkipListMap：執行緒安全版
• Guava Ordering + ImmutableList：不可變場景

// TreeMap 一行解決
Map<String, Integer> map = new TreeMap<>();
map.merge(sessionId, 1, Integer::sum);

何時手寫二分？

• 教學/面試展示演算法功底
• 極度受限環境（嵌入式、無標準庫）
• 需要自定義搜尋邏輯（如找第一個/最後一個等於、大於等於目標值的位置）