企业官网建设流程全解析

704. 二分查找 - 力扣（LeetCode）

前言：本题只是为了知识的完整性，往后使用二分算法都是用的第二道题的两个模板。

本题的暴力解法很简单，直接便利一遍数组然后比对每一个值，如果==target则说明找到了，便利完都没有找到就说明没有，返回-1。但是题目要求我们用时间复杂度O(logN)的算法去解决这个问题，那我们就要多观察一下题目的条件了。

二分的时间复杂度：首先先补充一个细节，上边的示例里我选择的3并不是中间的元素，那二分为什么要选择中间的元素？这个跟概率统计学有关系，具体就不必多深究了。总共n个长度的数组，循环一次，长度变成n/2，循环两次，长度变成n/2^2......循环k次，长度变成n/2^k==1，因此k==logN，时间复杂度就是O(logN)。

class Solution { public: int search(vector<int>& 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. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { //边界情况特殊判断一下 if(nums.empty()) return {-1, -1}; vector<int> 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的第一个元素的位置，也就是说根据>=target，<target这样的分段最终出循环的时候的l/r就是我们要的结果，因为这个模板找的就是>=target的第一个元素，那像示例3这种情况，区间里的元素全是<target的，那就需要额外判断一下，最终返回的应是l+1。

class Solution { public: int searchInsert(vector<int>& 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(vector<int>& 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(vector<int>& 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(vector<int>& 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]; } };

最后总结一下，二分算法出循环要不要判断l==r位置的数得看实际题目。