要求数组有序

mid=left+(left-right)/2     //防止int溢出每次缩小一半

时间复杂度O（log n）：每次缩小一半区间

空间复杂度O（1）

缺点：只适用有序数据。如果对于无序数据，专门排序（通常时间复杂度为O（nlog n））得不偿失。

对于经常插入元素的场景，为保持数组有序，需要插入指定位置，时间复杂度为O（n）

只适用于数组，因为需要非连续访问元素，因此不适合链表和基于链表实现的数据结构

当n很小时，线性查找更快，因为线性查找每轮只需执行1次判断操作，二分查找需要1次加法，1次除法，1~3次判断，1次加法（或减法）

二分查找插入元素：

Question

给定一个长度为n 的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引。

思考一：当数组中包含 target 时，插入点的索引是否是该元素的索引？

题目要求将 target 插入到相等元素的左边，这意味着新插入的 target 替换了原来 target 的位置。也就是说，当数组包含 target 时，插入点的索引就是该 target 的索引。

思考二：当数组中不存在 target 时，插入点是哪个元素的索引？

进一步思考二分查找过程：当 nums[m] < target 时 i 移动，这意味着指针 i 在向大于等于 target 的元素靠近。同理，指针 j 始终在向小于等于 target 的元素靠近。

因此二分结束时一定有：i 指向首个大于 target 的元素，j 指向首个小于 target 的元素。易得当数组不包含 target 时，插入索引为 i 。

若数组存在重复元素，要求插入第一个target，又会如何？

非target元素重复无影响，若target重复，无法知道二分查找得到的targe是第几个，可以向左线性查找（不推荐）

思考：

当 nums[m] < target 或 nums[m] > target 时，说明还没有找到 target ，因此采用普通二分查找的缩小区间操作，从而使指针 i 和 j 向 target 靠近。

当 nums[m] == target 时，说明小于 target 的元素在区间 [ i,  m-1 ] 中，因此采用 j=m-1 来缩小区间，从而使指针 j 向小于 target 的元素靠近。

循环完成后，i 指向最左边的 target ，j 指向首个小于 target 的元素，因此索引 i 就是插入点。

因此函数返回  i

无论何种情况，i 都是插入点的数组下标

二分查找找到左边界：

Question

给定一个长度为 n 的有序数组 nums 。请返回数组中最左一个元素 target 的索引。若数组中不包含该元素，则返回 -1 。

若target在数组内部，则与插入target情况相同。如果不在呢？

情况一：数组中既有>target又有<target的元素

此时返回的 i 为插入点，nums[ i ] != target,返回 -1 。

情况二：数组中只有>target的元素

target最小，所以应插入nums[ 0 ]，因此 i = 0（无论何种情况，i 都是插入点的数组下标）

nums[ i ] != target,返回 -1 。

情况三：数组中只有<target的元素

target最大，所以应插入nums[ n ]（此处越界），因此 i = n（无论何种情况，i 都是插入点的数组下标）

i 越界，返回-1

因此可以总结为

if (i == n || nums[ i ] != target) 

    return -1;

else

   return i ;

二分查找找到右边界：

可以仿照找左边的方法，但是需要微调

微调