【编程笔记】二分查找·数的范围

二分查找的思路

先找到那个有序序列的中间元素mid，然后拿它和要找的元素进行比较，就可以初步判断元素所在范围，既然查找范围已确定，自然该范围之外的元素就可以不用再查找了，然后按照上面的步骤反复查找下去。

折半查找要求查找表进顺序储拼且按关键字有序排列，因此对表进行元素的插入和删除时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况。

前提条件：查找的序列必须有序

时间复杂度：O（logn）

二分查找一般应用于满足某条件的第一/最后一个数，查找最大/最小值的情况。

此外，在二分查找中，还存在左右边界的问题。

比如查找的是7，有重复的俩个7，由此需要划分左右边界。

bSearchL和bSearchR的最大区别就是mid这一条件的设置，前者将区间[l, r]划分成[l, mid]和[mid + 1, r]，后者将区间[l, r]划分成[l, mid - 1]和[mid, r]。而(l+r)>>1和(l+r+1)>>1的区别在于，(l+r+1)>>1进行了向上取整。

至于最后返回值的时候，返回l和r皆是可行的，因为最后一定 r==l，下面的l,r写法只是为了方面区分。

而同时获取左右边界就是数的范围问题了。

数的范围问题

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

数的范围的过程

1.查找左边界

2.判断左边的元素是否存在（如果左边界查不到，说明这个数不存在序列中，直接返回，如果左边界能查询到，说明这个数存在于序列中，那就一定存在右边界）

3.根据判断结果查找并返回返回右边界

偷懒，今天没怎么进行学习。