算法篇：二分查找

目录介绍查找数组中值算法模板左右边界模板实例二分查找easy在排序数组中查找元素的第一个和最后一个medium搜索插入位置easyx 的平方根easy山峰数组的峰顶easy寻找峰值medium搜索旋转排序数组中的最小值medium0〜n-1 中缺失的数字easy介绍核心思想每次都通过比较中间元素将查找范围缩小一半直到找到目标或确认目标不存在。必要条件数据结构一定要是有序的升序或降序支持随机访问如数组、列表链表不适合查找数组中值算法模板左右边界模板左边界右边界如何确定题目到底是用哪个边界的算法呢可以直接假设mid在我们想找的答案上然后根据上面的模板和判断条件的要求看看要缩小那一边的区域。左边界找的是满足判断条件的第一个数右边界是找满足条件的第二个数实例二分查找easy704. 二分查找 - 力扣LeetCode该题目中的数组是升序的可以考虑用二分查找。算法流程a. 定义 left right 指针分别指向数组的左右区间。b. 找到待查找区间的中间点 mid 找到之后分三种情况讨论arr[mid] target 说明正好找到返回 mid 的值arr[mid] target 说明 [mid, right] 这段区间都是大于 target 的因此舍去右边区间在左边 [left, mid -1] 的区间继续查找即让 right mid -1 然后重复 2 过程arr[mid] target 说明 [left, mid] 这段区间的值都是小于 target 的因此舍去左边区间在右边 [mid 1, right] 区间继续查找即让 left mid 1 然后重复 2 过程c. 当 left 与 right 错开时说明整个区间都没有这个数返回 -1 。class Solution { public: int search(vectorint nums, int target) { int left0,rightnums.size()-1; while(leftright)//// 由于两个指针相交时当前元素还未判断因此需要取等号 { int midleft(right-left)/2; if(nums[mid]target)leftmid1; else if (nums[mid]target)rightmid-1; else return mid; } return -1; } };在排序数组中查找元素的第一个和最后一个medium34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode题目解析在一个升序数组中找到一段全是目标值的区间返回全是目标值的第一个下标和最后一个目标值的下标。假设左边界下标是resleft目标值为x右边界下标为resright寻找左边界思路根据左边界进行划分成两个区域[left,resleft-1]都是小于x的[resleft,right]都是大于等于x的因此根据mid的落点我们可以分为两个情况当mid落在[left,resleft-1]区域内是即nums[mid]x,那么这个区域内的值是可以全部舍去的所以让leftmid1,继续在[mid1right]中寻找左边界当mid落在[resleftright]区域内即nums[mid]x,说明[mid1,right]可以舍去但mid位置可能是最终结果所以right更新成mid继续在[left,mid]中寻找左边界寻找右边界思路根据右边界进行划分成两个区域[left,resright]都是小于等于x的[resright1,right]都是大于x的因此根据mid的落点我们可以分成两种情况当mid落在[left,resright]区域内是即nums[mid]x,那么[left,mid-1]的值是可以全部舍去的但mid位置可能是最终结果,所以让leftmid,继续在[midright]中寻找右边界当mid落在[resright1right]区域内即nums[mid]x,说明[mid,right]可以舍去所以right更新成mid-1继续在[left,mid-1]中寻找右边界细节部分中间值有两种取法midleft(right-left)/2 //向下取整midleft(right-left1)/2//向上取整当left和right即将相遇时可能出现死循环寻找左边界时假设left1,right2,leftmid1,rightmid,如果midleft(right-left1)/2那么mid2因为rightmid导致一直right都没有向前走一步让leftright让循环结束所以我们寻找左边界的时候要向下取整。同理可得右边界class Solution { public: vectorint searchRange(vectorint nums, int target) { int left0,rightnums.size()-1; if(nums.size()0)return {-1,-1}; while(leftright) { int midleft(right-left)/2; if(nums[mid]target)leftmid1; else rightmid; } int begin-1; if(nums[left]!target) return {-1,-1}; else beginleft; left0,rightnums.size()-1; while(leftright) { int midleft(right-left1)/2; if(nums[mid]target) leftmid; else rightmid-1; } return {begin,right}; } };搜索插入位置easy35. 搜索插入位置 - 力扣LeetCode题目解析在一个升序数组中找到target的下标如果target不存在就返回它在数组中处在什么下标可以让数组依旧是升序所在的下标。根据第二个案例假设mid在下标为1的地方然后当前数组中的下标为1的数大于target32)判断条件是nums[mid]与target的关系32,说明题意要求的值在左边所以可以直接舍去右边的值这时候就是right移动right有两种移动一个是rightmid,另一个是rightmid-1。如果选择第二个那么正确答案就被排除在外了所以选第一个第一个在左右边界模板中寻找左边界模板。解题思路假设target所在数组中的下标是i那么我们可以把数组分为两个区域[left,i-1]:全部小于target;[i,right]都是大于等于target根据这个区域划分我们可以知道其实这个题相当于找左边界。因此根据mid的落点我们可以分为两个情况当mid落在[left,i-1]区域内是即nums[mid]x,那么这个区域内的值是可以全部舍去的所以让leftmid1,继续在[mid1right]中寻找当mid落在[iright]区域内即nums[mid]x,说明[mid1,right]可以舍去但mid位置可能是最终结果所以right更新成mid继续在[left,mid]中寻找class Solution { public: int searchInsert(vectorint nums, int target) { int left0,rightnums.size(); while(leftright) { int midleft(right-left)/2; if(nums[mid]target) leftmid1; else rightmid; } return right; } };x 的平方根easy69. x 的平方根 - 力扣LeetCode题目解析找出x的平方根即给x开根号如果x开根号后有小数就只保留整数。根据第二个案例假设mid在等于2的地方然后当前数组中的2*2的数小于target48)找的值在右边所以舍去左边的值这时候就是left移动left有两种移动一个是leftmid,另一个是leftmid1。如果选择第二个那么正确答案就被排除在外了所以选第一个第一个在左右边界模板中寻找右边界模板。解题思路假设x的最终平方根结果是index把区域划分为两部分[left,index]的平方根全部都是小于等于x的[index1,right]的平方根全部大于x具有二分性因此根据mid的落点我们可以分成两种情况当mid落在[left,i]区域内是即nums[mid]x,那么[left,mid-1]的值是可以全部舍去的但mid位置可能是最终结果,所以让leftmid,继续在[midright]中寻找当mid落在[i1right]区i域内即nums[mid]x,说明[mid,right]可以舍去所以right更新成mid-1继续在[left,mid-1]中寻找class Solution { public: int mySqrt(int x) { long long left1,rightx; if(x0)return 0; while(leftright) { long long midleft(right-left1)/2; if(mid*midx)leftmid; else rightmid-1; } return left; } };山峰数组的峰顶easy852. 山脉数组的峰顶索引 - 力扣LeetCode题目解析在一个先单调递增然后单调递减的数组中找到单调递增的结束的最大值。峰值有个明显特征就是只要比后面的那个数大就是峰值。方法一暴力解法class Solution { public: int peakIndexInMountainArray(vectorint arr) { int n arr.size(); // 遍历数组内每⼀个元素直到找到峰顶 for (int i 1; i n - 1; i) // 峰顶满⾜的条件 if (arr[i] arr[i - 1] arr[i] arr[i 1]) return i; // 为了处理 oj 需要控制所有路径都有返回值 return -1; } };方法二根据峰值所在位置可以把数组分成两部分一部分单调递增一部分单调递减具有二分性。根据第二个案例假设mid在下标为1的地方然后当前数组中的下标为1的数大于后一个数说明目标值在左边前半部分单调递增可以舍去右边的区域这时候就是right移动right有两种移动一个是rightmid,另一个是rightmid-1。如果选择第二个那么正确答案就被排除在外了所以选第一个第一个就是左右边界模板中寻找左边界模板。解题思路假设target所在数组中的下标是i那么我们可以把数组分为两个区域[left,i-1]:全部小于target;[i,right]都是大于等于target根据这个区域划分我们可以知道其实这个题相当于找左边界。因此根据mid的落点我们可以分为两个情况当mid落在[left,i-1]区域内是即nums[mid]x,那么这个区域内的值是可以全部舍去的所以让leftmid1,继续在[mid1right]中寻找当mid落在[iright]区域内即nums[mid]x,说明[mid1,right]可以舍去但mid位置可能是最终结果所以right更新成mid继续在[left,mid]中寻找class Solution { public: int peakIndexInMountainArray(vectorint arr) { int left0,rightarr.size()-1; while(leftright) { int midleft(right-left)/2; if(arr[mid]arr[mid1])rightmid; else leftmid1; } return right; } };寻找峰值medium162. 寻找峰值 - 力扣LeetCode解题方法和上题一样class Solution { public: int findPeakElement(vectorint nums) { int left0,rightnums.size()-1; while(leftright) { int midleft(right-left)/2; if(nums[mid]nums[mid1])rightmid; else leftmid1; } return right; } };搜索旋转排序数组中的最小值medium153. 寻找旋转排序数组中的最小值 - 力扣LeetCode题目解析找一个数组中的最小值。这个数组中有两个都是单调递增的方法一暴力解法一直标记一个最小值进行比较class Solution { public: int findMin(vectorint nums) { int n nums.size(); int minnumINT_MAX; int index-1; // 遍历数组内每⼀个元素直到找到最小值 for (int i 0; i n; i) { if(nums[i]minnum) { minnummin(minnum,nums[i]); indexi; } } return nums[index]; } };方法二二分查找该数组有两部分单调递增具有二分性可以考虑二分查找判断条件的选择分析数组我们发现在最后的一个数的前面的值只有它前面几个数比它小其他都比它大所以我们的判断条件就是和最后一个数比较。左右边界的判断:我们要找的是第一个满足要求的数所以用左边界。解题思路假设target所在数组中的下标是i那么我们可以把数组分为两个区域[left,i-1]:全部小于target;[i,right]都是大于等于target根据这个区域划分我们可以知道其实这个题相当于找左边界。因此根据mid的落点我们可以分为两个情况当mid落在[left,i-1]区域内是即nums[mid]x,那么这个区域内的值是可以全部舍去的所以让leftmid1,继续在[mid1right]中寻找当mid落在[iright]区域内即nums[mid]x,说明[mid1,right]可以舍去但mid位置可能是最终结果所以right更新成mid继续在[left,mid]中寻找class Solution { public: int findMin(vectorint nums) { int left0,rightnums.size()-1; //找最小值 int xnums[right]; while(leftright) { int midleft(right-left)/2; if(nums[mid]x)rightmid; else leftmid1; } return nums[left]; } };0〜n-1 中缺失的数字easyLCR 173. 点名 - 力扣LeetCode题目解析在一个按顺序排列的数组中找缺的数。数组单调递增可以考虑二分查找。方法一暴力解法class Solution { public: int takeAttendance(vectorint records) { if(records.size()1records[0]0)return 1; for(int i0;irecords.size();i) { if(i!records[i])return i; } int nrecords.size()-1; if(nrecords[n]) return n1; else return -1; } };方法二二分查找判断条件可以舍去一部分的条件如果midrecords[mid]是不是说明前面一部分的都没有缺人所以前面一部分可以舍去让leftmid1假设target所在数组中的下标是i那么我们可以把数组分为两个区域[left,i-1]:全部小于target;[i,right]都是大于等于target根据这个区域划分我们可以知道其实这个题相当于找左边界。因此根据mid的落点我们可以分为两个情况当mid落在[left,i-1]区域内是即nums[mid]mid,那么这个区域内的值是可以全部舍去的所以让leftmid1,继续在[mid1right]中寻找当mid落在[iright]区域内即nums[mid]!mid,说明[mid1,right]可以舍去但mid位置可能是最终结果所以right更新成mid继续在[left,mid]中寻找class Solution { public: int takeAttendance(vectorint records) { if(records.size()1records[0]0)return 1; int left0,rightrecords.size()-1; while(leftright) { int midleft(right-left)/2; if(midrecords[mid])leftmid1; else rightmid; } return leftrecords[left]?left1:left; } };