算法入门（三）：二分查找 - 基础模板 边界控制（Leetcode 704/35/278/34/69/367）
二分查找二分查找指在有序数组中每次排除一半的可能性查找剩下的范围中符合条件的值。二分排除一半选择一半有序数据必须有序边界处理left right 还是 left rightleft mid 1 还是 left mid题单阶段顺序题目难度核心训练基础模板1Binary Search (LeetCode 704)⭐标准二分模板找 target基础模板2Search Insert Position (LeetCode 35)⭐找不到时返回插入位置基础模板3First Bad Version (LeetCode 278)⭐单调性、找第一个满足条件的位置边界控制4Find First and Last Position (LeetCode 34)⭐⭐左边界 / 右边界边界控制5Sqrt(x) (LeetCode 69)⭐⭐找满足条件的最大值边界控制6Valid Perfect Square (LeetCode 367)⭐⭐边界判断、防溢出旋转数组7Find Minimum in Rotated Sorted Array (LeetCode 153)⭐⭐⭐旋转数组入门局部有序旋转数组8Search in Rotated Sorted Array (LeetCode 33)⭐⭐⭐在旋转数组中找 target旋转数组9Search in Rotated Sorted Array II (LeetCode 81)⭐⭐⭐⭐含重复元素的旋转数组答案二分10Koko Eating Bananas (LeetCode 875)⭐⭐⭐⭐二分答案模板答案二分11Capacity To Ship Packages Within D Days (LeetCode 1011)⭐⭐⭐⭐复杂 check 函数模板区间语义区间表示right初始值right是否参与搜索循环条件退出条件left right时闭区间[left, right]len - 1是left rightleft right仍有 1 个元素左闭右开[left, right)len否left rightleft right区间为空704入门题目本方法基于leftright和闭区间思考得来。classSolution{public:intsearch(vectorintnums,inttarget){intnnums.size();intleft0;intrightn-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){rightmid-1;}elseif(nums[mid]target){leftmid1;}else{returnmid;}}return-1;}};35classSolution{public:intsearchInsert(vectorintnums,inttarget){intnnums.size();intleft0;intrightn-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){rightmid-1;}elseif(nums[mid]target){leftmid1;}else{returnmid;}}returnnums[left]target?left:left1;}};278// The API isBadVersion is defined for you.// bool isBadVersion(int version);classSolution{public:intfirstBadVersion(intn){intleft1;intrightn;while(leftright){intmidleft(right-left)/2;if(isBadVersion(mid)){rightmid-1;}else{leftmid1;}}returnleft;}};3469classSolution{public:intmySqrt(intx){intleft0;intrightx;while(leftright){intmidleft(right-left)/2;longlongsqrt;sqrt(longlong)mid*mid;if(sqrtx){rightmid-1;}elseif(sqrtx){leftmid1;}else{returnmid;}}returnright;}};367
