二分查找之按照左闭右开区间查找

想必大家不会感到陌生，二分查找是一种在‌有序数据‌中快速找目标的方法，也叫折半查找。它通过不断缩小范围来定位，效率很高。

查找右边界：缩小左边界范围

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

• 当nums[mid] == target时，新区间划定为right = mid，而结束时left = right，所以这里left或者right就是结果。

查找左边界：缩小右边界范围

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

当 nums[mid] == target 时，新区间划定为 left = mid + 1，所以结束时left不是等于最后一个mid，mid = left - 1