C# BinarySearch 返回值的具体使用

binarySearch()方法的返回值为：

返回值	含义
≥ 0	找到元素，返回其在集合中的索引位置
< 0	未找到元素，返回一个负数

1、如果找到关键字，则返回值为关键字在数组中的位置索引，且索引从0开始

2、如果没有找到关键字，返回值为负的插入点值，所谓插入点值就是第一个比关键字大的元素在数组中的位置索引，而且这个位置索引从1开始。

未找到时的负数值

当元素未找到时，返回值是一个负数，其计算公式为：

返回值 = ~(插入点索引)

或等价于：

插入点索引 = ~返回值

插入点 = 如果将该元素插入集合中，它应该所在的位置（保持排序顺序）。

假设有排序数组：[10, 20, 30, 40, 50]

情况1：查找 25（不存在）

// BinarySearch 查找 25
// 应该插入在 20 和 30 之间，也就是索引 2 的位置，但是索引从1开始，所以变成3，再取负值，就是-3
int index = BinarySearch(25);  // 返回 -3
//-3使用 ~（按位取反）可以得到从0开始的插入点值
int insertIndex = ~index;       // ~(-3) = 2
// insertIndex = 2

情况2：查找 5（比所有值都小）

// BinarySearch 查找 5
// 应该插入在最前面，索引 0 的位置
// 所以返回：-1
int index = BinarySearch(5);    // 返回 -1
int insertIndex = ~index;       // ~(-1) = 0
// insertIndex = 0

情况3：查找 60（比所有值都大）

// BinarySearch 查找 60
// 应该插入在最后，索引 5 的位置（数组长度）
// 所以返回： -6
int index = BinarySearch(60);   // 返回 -6
int insertIndex = ~index;       // ~(-6) = 5
// insertIndex = 5