使用二分查找优化时间复杂度

        二分查找，也称为折半查找，是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。我们应该如何用在具体问题中呢？

题目链接（力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台）

 

可以直接通过遍历一次数组就得到对应值下标了，时间复杂度为 。但是我们可以通过划分区间的方式获得更优秀的时间复杂度（二分查找），通过取中值的方式可以把一个数组划分出两个区间，通过中值可以判断出target在哪一个区间，循环迭代即可。按照这种方式我们可以一次舍去一整片区间，相比于遍历数组一次舍去一个数值，得到的时间复杂度为 。 具体细节见代码： int search(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while(left <= right){ int mid = (left + right)/2; if(nums[mid] > target) //要查找的目标值在左区间 right = mid - 1; else if(nums[mid] < target) //要查找的目标值在右区间 left = mid + 1; else return mid; } return -1; }

题目链接（力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 ）

 

我们依旧可以通过一次遍历完成，定义两个指针分别记住target值的第一次出现的下标，第二个指针记住target值最后一次出现的下标即可，时间复杂度为 。题目要求时间复杂度为 ，我们采用上面这种二分查找算法会有一些问题，因为如果我们有一个数组 nums = [5, 5, 5, 5, 5, 5 ,5], target = 5 ，我们获得的mid既不知道开头下标也不知道结尾下标。也就是说，当mid等于target值的时候，我们需要额外做一些事情。 具体细节见代码： vector<int> searchRange(vector<int>& nums, int target) { if(nums.size() == 0) return {-1, -1}; int begin = 0, end = 0; //处理begin int left = 0, right = nums.size()-1; while(left < right){ int mid = (left + right)/2; if(nums[mid] < target) //目标值在右区间 left = mid + 1; else right = mid; } if(nums[left] != target) return {-1, -1}; else begin = left; //处理end left = 0, right = nums.size()-1; while(left < right){ int mid = (left + right + 1)/2; if(nums[mid] <= target) //目标值在右区间 left = mid; else right = mid - 1; } end = right; return {begin, end}; }

所以不管是区间还是单个元素的问题，我们可以总结一个通用的模版：

处理区间左端点：

int left = 0, right = nums.size()-1; while(left < right){ int mid = (left + right)/2; if(nums[mid] < target) left = mid + 1; else right = mid; }

        通过 nums[mid] < target 这个条件来不断逼近目标值区间的左端点，最终left和right一起指向目标值区间的左端点。

处理区间右端点：

int left = 0, right = nums.size()-1; while(left < right){ int mid = (left + right + 1)/2; if(nums[mid] <= target) left = mid; else right = mid - 1; }

        通过 nums[mid] > target 这个条件来不断逼近目标值区间的右端点，最终left和right一起指向目标值区间的右端点。

注意： 1. 为什么在while循环的时候我们判断条件使用的是 left < right 而不是 left <= right 呢？         以处理目标值区间的左端点为例：         根据if else里的条件，left只会在target的左边的区间内移动，不会越过target，也就是说left可以移动到的最右边的位置正好是target的开始位置（如果符合条件的target只有一个，则就是这个元素的位置）；         right同理，也会在右边的区间移动，不会越过target，right可以移动到的最左边的位置正好是target的结束位置（如果符合条件的target只有一个，则就是这个元素的位置）；         根据以上两点分析，当 left = right 的时候一定是最终结果，要么是target的位置，要么就是无解。如果我们使用的是 left <= right ，当 left = right 的时候还会继续进入循环，循环没有突破边界的可能（即不可能出现left > right的可能），程序就会死循环。 2. 在求中点的时候要向下取整，避免在极端情况下（如果向上取整的话，如果此刻三个下标的位置是nums = [..., left, mid 和 right, ... ]，如果下一次循环依旧是更新right的话，三个下标的位置还是nums = [..., left, mid 和 right, ... ]）程序进入死循环。同理，在处理右端点的时候需要向上取整。