ash*_*bar 5 java binary-search data-structures
从文档引用它说java.util.Collections.binarySearch(List<? extends Comparable<? super T>> list, T key)返回...
搜索关键字的索引,如果它包含在列表中; 否则,( - (插入点) - 1).插入点定义为键将插入列表的点:第一个元素的索引大于键,或者list.size(),如果列表中的所有元素都小于指定的键. .
我的问题是,这个定理(-(insertion point) - 1)有什么意义(如果有的话),以至于当找不到密钥时它是返回值？为什么不返回insertion point例如？
首先，如果没有找到该元素，必须根据文档返回负值，否则无法区分找到和未找到。
好的，那为什么不只是-insertion point？想象一下，如果插入点为 0（搜索到的元素小于所有现有元素），那么该逻辑就会中断——未找到将返回一个非负数。因此额外的-1.
好的，那为什么不-1总是这样呢？
因为知道排序列表中不匹配项的插入点对于找到以下问题的答案很有用：
下一个比我要求的元素大的元素是什么？
和
有多少元素比我（没有）找到的元素大？
而且，二进制搜索的工作方式，算法在终止时知道这个索引，那么为什么不在不需要额外费用的情况下共享它呢？