优选算法---专题3(二分查找算法)

704. 二分查找 - 力扣LeetCode前言本题只是为了知识的完整性往后使用二分算法都是用的第二道题的两个模板。本题的暴力解法很简单直接便利一遍数组然后比对每一个值如果target则说明找到了便利完都没有找到就说明没有返回-1。但是题目要求我们用时间复杂度O(logN)的算法去解决这个问题那我们就要多观察一下题目的条件了。二分的时间复杂度首先先补充一个细节上边的示例里我选择的3并不是中间的元素那二分为什么要选择中间的元素这个跟概率统计学有关系具体就不必多深究了。总共n个长度的数组循环一次长度变成n/2循环两次长度变成n/2^2......循环k次长度变成n/2^k1因此klogN时间复杂度就是O(logN)。class Solution { public: int search(vectorint nums, int target) { int n nums.size(); int l 0, r n - 1; while(l r) { //int mid (l r) / 2; //防止int溢出r肯定l所以用r-l int mid l (r - l) / 2; if(nums[mid] target) { r mid - 1; } else if(nums[mid] target) { l mid 1; } else { return mid; } } return -1; } };34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCodeclass Solution { public: vectorint searchRange(vectorint nums, int target) { //边界情况特殊判断一下 if(nums.empty()) return {-1, -1}; vectorint ret; //找左端点 int n nums.size(); int l 0, r n - 1; while(l r) { int mid l (r - l) / 2; if(nums[mid] target) { r mid; } else { l mid 1; } } //需不需要出循环之后再判断一下是根据题目意思来的 //像本题有可能不存在要返回{-1,-1}因此出循环之后还要判断一下 if(nums[l] target) ret.push_back(l); else return {-1, -1}; //找右端点 l 0, r n - 1; while(l r) { int mid l (r - l 1) / 2; if(nums[mid] target) { r mid - 1; } else { l mid; } } if(nums[l] target) ret.push_back(l); else return {-1, -1}; return ret; } };69. x 的平方根 - 力扣LeetCode这里多说一下上边模板的记忆方法其实主要需要记忆的地方就是计算mid是否1如果if-else里有1则mid就不用1如果没有就需要。求一个数的平方根比如说根号16得到的是正负4算数平方根就是取正的那个也就是4。先想想暴力解题目要求的是一个数的算数平方根的整数部分那我们就枚举整数呗而且要的是算数平方根那就枚举正整数比如说求17的算数平方根从1开始枚举。一旦有了上边的分析马上就知道本题肯定是用二分因为本题就是在众多的平方根里找到一个正确的平方根因此我们就枚举1~x的所有数字。class Solution { public: int mySqrt(int x) { int l 1, r x; while(l r) { long long mid l (r - l 1) / 2; //mid得用long long来存因为int*int结果还是int就会溢出 //导致下边的判断不对了 if(mid * mid x) { r mid - 1; } else { l mid; } } if(l * l x) return l; return 0; } };35. 搜索插入位置 - 力扣LeetCode数组是升序的且无重复元素题目的意思说白了就是找target第一次出现的位置根据数组升序区间自然分为两段一段target一段target也行。为什么呢因为根据题目的示例target如果存在那没关系直接返回l如果不存在target应该插入在target的第一个元素的位置也就是说根据targettarget这样的分段最终出循环的时候的l/r就是我们要的结果因为这个模板找的就是target的第一个元素那像示例3这种情况区间里的元素全是target的那就需要额外判断一下最终返回的应是l1。class Solution { public: int searchInsert(vectorint nums, int target) { int l 0, r nums.size() - 1; while(l r) { int mid l (r - l) / 2; if(nums[mid] target) { l mid 1; } else { r mid; } } if(nums[l] target) return l 1; return l; } };852. 山脉数组的峰顶索引 - 力扣LeetCode首先肯定是从暴力解法入手本题要求找的是峰顶元素峰顶元素的特点肯定就是比其左边紧挨着的元素大比其右边紧挨着的元素大呈现出一个山峰的样子暴力解法就是从头到尾便利数组每便利到一个元素都去看看该元素是否比前一个元素大比后一个元素大直至找到第一个满足这样条件的元素即为峰顶整体时间复杂度就为O(N)。接下来去优化一下暴力解法根据山峰的特点整个区间天然的被分成了两个部分区间具具有二段性就可用二分。class Solution { public: int peakIndexInMountainArray(vectorint arr) { int l 0, r arr.size() - 1; while(l r) { int mid l (r - l 1) / 2; if(arr[mid] arr[mid - 1]) { l mid; } else { r mid - 1; } } //题目保证了肯定是有峰值的因此出循环后直接返回l即可 return l; } };162. 寻找峰值 - 力扣LeetCode第一种暴力解法寻找峰值肯定是从前往后便利数组去找跟上题不同的是本题可能存在多个峰值如下图就是暴力解法会产生的三种情况时间复杂度为O(N)因为最差情况就是数组一直递增到最后一个元素。优化一下假设现在有nums[i]和nums[i 1]这两个数。由以下分析可知区间存在二段性因此可以用二分算法nums[mid] nums[mid 1]r mid不要mid-1因为此时的mid有可能是峰值(如下图)。nums[mid] nums[mid 1]l mid 1。class Solution { public: int findPeakElement(vectorint nums) { int l 0, r nums.size() - 1; while(l r) { int mid l (r - l) / 2; //题目保证了nums[i] ! nums[i 1] if(nums[mid] nums[mid 1]) { r mid; } else { l mid 1; } } return l; } };153. 寻找旋转排序数组中的最小值 - 力扣LeetCode题目的意思是原来有一个升序的数组但在给你之前它先旋转了1~n里的任意次数现在要找的是数组里最小的元素。旋转之前严格升序则旋转之后大的数跑前边了小的数跑后边了数组呈现出了一个二段性。下边分析里还要补一句题目里没有重复的元素则出循环后就没必要再判断了就是结果了。暴力解法就不说了无非就是便利一遍或者排序。class Solution { public: int findMin(vectorint nums) { int n nums.size(); int l 0, r n - 1; while(l r) { int mid l (r - l) / 2; if(nums[mid] nums[n - 1]) { l mid 1; } else { r mid; } } return nums[l]; } };最后总结一下二分算法出循环要不要判断lr位置的数得看实际题目。