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

想必大家不会感到陌生二分查找是一种在‌有序数据‌中快速找目标的方法也叫折半查找。它通过不断缩小范围来定位效率很高。查找右边界缩小左边界范围int binarySearch(vectorint 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(vectorint 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不是等于最后一个midmid left - 1