把二分查找的负数接到插入操作：实现一个有序编码目录

Arrays.binarySearch 查不到元素时，不是统一返回 -1。对 [10, 20, 30] 查找 5、25、40，会得到不同负数，因为结果同时携带了保持排序所需的插入位置。把它写成 if (index == -1)，只有少数缺失值能走进正确分支。

这篇教程把这个返回合同接到一个小型商品编码目录：目录有序、编码唯一，插入后保留旧版本，非法编码与重复编码都明确失败。它适合学习“查找结果怎样变成后续操作”，并不打算把数组包装成万能数据库索引。

负数里存了什么

未找到时，返回值为 -(插入位置) - 1，因此还原使用 -result - 1。插入位置允许等于数组长度，表示放到末尾；也允许是零，表示放到开头。额外减一使位置零能用负数表达，避免与下标零的命中结果混在一起。

判断成功只能用 result >= 0，失败用 result < 0。不能用绝对值当插入位置，也不能在所有情况下先取负数；命中时结果本来就是数组下标。本例把这两条路径保留在同一段代码中，让分支含义可以直接核查。

二分查找要求输入已经按相同规则排序。拿一个碰巧在某次运行中返回正确下标的乱序数组，不能证明算法能处理乱序。目录创建时会复制并排序，后续每次插入也维护这个条件；外部无法拿到内部数组再任意改值。

可运行的目录实现

环境为 Java 17，无第三方依赖。保存为 SortedCatalog.java 后执行 java SortedCatalog.java。程序同时包含小数组定位、目录插入和重复值区间的演示。

import java.util.*;

public class SortedCatalog {
    static final class Catalog {
        private static final int MAX_ENTRIES = 10000;
        private final String[] codes;
        private Catalog(String[] owned) { this.codes = owned; }
        static Catalog of(String... input) {
            if (input.length > MAX_ENTRIES) throw new IllegalArgumentException("catalog full");
            String[] copy = input.clone();
            for (String code : copy) validate(code);
            Arrays.sort(copy);
            for (int i = 1; i < copy.length; i++) {
                if (copy[i - 1].equals(copy[i])) throw new IllegalArgumentException("duplicate code");
            }
            return new Catalog(copy);
        }
        static void validate(String code) {
            if (code == null || !code.matches("[A-Z][0-9]{3}"))
                throw new IllegalArgumentException("invalid code");
        }
        Catalog insert(String code) {
            validate(code);
            int result = Arrays.binarySearch(codes, code);
            if (result >= 0) throw new IllegalArgumentException("duplicate code");
            if (codes.length == MAX_ENTRIES) throw new IllegalArgumentException("catalog full");
            int position = -result - 1;
            String[] next = new String[codes.length + 1];
            System.arraycopy(codes, 0, next, 0, position);
            next[position] = code;
            System.arraycopy(codes, position, next, position + 1, codes.length - position);
            return new Catalog(next);
        }
        boolean contains(String code) {
            validate(code);
            return Arrays.binarySearch(codes, code) >= 0;
        }
        @Override public String toString() { return Arrays.toString(codes); }
    }
    static int lowerBound(int[] a, int key) {
        int low = 0, high = a.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (a[mid] < key) low = mid + 1;
            else high = mid;
        }
        return low;
    }
    static int upperBound(int[] a, int key) {
        int low = 0, high = a.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (a[mid] <= key) low = mid + 1;
            else high = mid;
        }
        return low;
    }
    public static void main(String[] args) {
        int[] numbers = {10, 20, 30};
        for (int key : new int[]{5, 20, 25, 40}) {
            int result = Arrays.binarySearch(numbers, key);
            System.out.println("key=" + key + ", result=" + result
                    + (result < 0 ? ", insert=" + (-result - 1) : ", hit=" + result));
        }
        System.out.println("range-result=" + Arrays.binarySearch(new int[]{10,20,30,40,50}, 1, 4, 25));
        Catalog original = Catalog.of("B200", "A100");
        Catalog changed = original.insert("A050").insert("B150").insert("C300");
        System.out.println("original=" + original);
        System.out.println("changed=" + changed);
        System.out.println("found=" + changed.contains("B150"));
        System.out.println("empty-insert=" + Catalog.of().insert("A001"));
        try { changed.insert("A100"); }
        catch (IllegalArgumentException e) { System.out.println(e.getMessage()); }
        try { changed.insert("a100"); }
        catch (IllegalArgumentException e) { System.out.println(e.getMessage()); }
        int[] duplicates = {2, 2, 2, 3};
        int left = lowerBound(duplicates, 2), right = upperBound(duplicates, 2);
        System.out.println("equal-range=[" + left + "," + right + ")");
        if (left != 0 || right != 3) throw new AssertionError("duplicate range");
        for (int key = 0; key <= 40; key++) {
            int result = Arrays.binarySearch(numbers, key);
            if (result >= 0) {
                if (numbers[result] != key) throw new AssertionError("wrong hit");
            } else {
                int p = -result - 1;
                if (p > 0 && numbers[p-1] >= key) throw new AssertionError("left bound");
                if (p < numbers.length && numbers[p] <= key) throw new AssertionError("right bound");
            }
        }
        System.out.println("positions=verified");
    }
}

key=5, result=-1, insert=0
key=20, result=1, hit=1
key=25, result=-3, insert=2
key=40, result=-4, insert=3
range-result=-3
original=[A100, B200]
changed=[A050, A100, B150, B200, C300]
found=true
empty-insert=[A001]
duplicate code
invalid code
equal-range=[0,3)
positions=verified

最前面的结果可以拿纸笔重算：5 应插到零位，所以返回 -1；25 插到下标二，返回 -3；40 放到末尾下标三，返回 -4。命中 20 时返回下标一，与这些编码规则无关。

范围重载也值得单独看。fromIndex=1、toIndex=4 表示只搜索这个半开范围，但返回的命中下标和插入位置仍按原数组坐标解释，不是从范围开头重新计数。样例找 25 的插入位置为二，所以依然返回 -3；如果再把 fromIndex 加一次，就会移错位置。

插入操作如何保护旧目录

构造函数只接收当前实现拥有的数组。公开的 of 先 clone 输入，防止调用者之后修改传入数组破坏目录排序。它接受乱序输入，但拒绝重复值；这个决定写在工厂里，不会把历史重复数据悄悄合并掉。

insert 先定位，若已经存在就拒绝；不存在才分配新数组。左半段复制到原位置，空出的一格写新值，右半段整体后移一格。数组长度已经限定在一万以内，因此 length + 1 不会靠近整数溢出边界；这个上限是教程目录的容量策略，并非 Java 数组的统一最大长度。

运行结果里的 original 没有随 changed 增长。这是版本式更新的直接结果，不是列表包装的副作用。失败时也不会把一半数据写进旧数组：所有修改发生在局部新数组中，返回成功之前旧版本保持不变。调用者仍然要决定把新版本保存到哪里，代码不会自动替换外部引用。

编码规范只允许一个大写字母加三位数字，所以自然字符串顺序与本目录的编码顺序可以一致使用。没有在比较过程中偷偷做大小写转换，也没有把输入 a100 合并到 A100。若需求改为忽略大小写，排序、搜索与判重必须一起换成同一个比较合同；只给查找方法补一个 Comparator 会破坏已有有序条件。

命中重复值，不能拿一个下标代表整个范围

标准 binarySearch 遇到多个相等元素时，只保证返回其中一个，不承诺第一个或最后一个。目录通过唯一性约束避开了这个歧义，但别把这项业务约束误当成 API 特性。日志按时间分组、成绩按分数归类时，相等键通常确实存在。

完整程序另外给出了 lowerBound 和 upperBound：前者找第一个不小于 key 的位置，后者找第一个大于 key 的位置。两者构成的半开区间正好覆盖全部等值元素。样例三个 2 得到 [0,3)，区间长度也是重复数量。没有命中时，两个位置相等，表示空区间。

两个循环使用 [low, high) 作为剩余搜索范围，high 可以等于长度，但中点永远是合法元素下标。更新为 mid 或 mid+1 都会缩小范围，不需要在循环末尾补一段不稳定的“再试一个元素”。中点写成 low + (high - low) / 2，也避免直接相加可能产生的下标溢出。

末尾对零到四十的每个键验证插入条件：位置左侧严格小于缺失键，右侧严格大于缺失键。这是本例无重复数组的性质断言，比只检查三条固定输出更能发现符号还原错误。对于允许重复的通用边界查找，相应不等号规则应按 lower/upper 的定义调整，不能原样套用。

如果对边界循环仍然没有把握，可以跟踪查找 25 的 lowerBound：起点是 low=0、high=3，中点一上的值 20 偏小，于是 low 变成二；接着中点二上的值 30 不小于目标，于是 high 变成二。范围为空，返回二。整个过程并不需要数组里真的存在 25，因此同一套循环同时处理命中与缺失。

upperBound 只把比较条件改成小于等于，却改变了相等值该归入哪一侧。这一处差异决定了它越过整段等值元素。对于按时间查询的有序数据，先明确起止时间是否包含，再选择相应边界；先随意取一个命中下标、再向两侧扫描，不仅重复工作，也容易漏掉没有命中的端点。

不要把数组上的复杂度结论无条件移给任意 List。链式列表访问中点还要沿链接移动，比较次数少不代表总访问成本相同。若目录已经以数组或支持高效随机访问的结构保存，二分定位才与这里的模型一致。为了调用同一个方法临时复制大集合，也应把复制成本算进一次完整操作，而不是只讨论搜索循环。

数组目录适合怎样的更新节奏

查找只需对数次比较，但插入仍要复制数组，整体是线性工作。用二分确定插入位置，并没有把搬移元素也变成对数复杂度。大量随机写入时，应重新考虑有序树、批量归并或既有存储索引；这里没有给出不经验证的性能数字。

只读为主、目录不大、成批生成新版本的场景，则可以从这种不可变数组布局受益。若一次追加几千项，通常应先验证并排序新批次，再与旧版本归并，而不是连续调用 insert 制造大量中间数组；批次内重复与跨版本重复依旧需要明确处理。

多线程同时基于同一旧版本生成新目录，还可能出现最后一次赋值覆盖前一更新的问题。内部数组不变，不代表外部更新天然原子。需要由所属服务用锁或版本比较约束替换动作；本文的单线程程序没有宣称已经完成并发目录管理。

空目录、开头插入、中间插入、末尾插入、重复拒绝和非法编码，分别覆盖了可见的几个边界。迁移真实编码规则时，先替换这些样本和验证合同，再考虑把对象类型换成更复杂的商品条目，能够让下标计算与业务判断保持各自清晰。