企业官网建设流程全解析

二分算法

二分算法（Binary Search）是一种在有序数组中高效查找目标值的算法，核心思想是每次将搜索区间对半缩小，从而把时间复杂度从线性 O(n) 降到对数级 O(log n)。

它的适用前提是数组具有二段性——即存在一个分界点，使得分界点两侧的元素满足不同的性质。只要满足这一条件，就可以通过不断比较中间元素与目标值，逐步缩小搜索范围，最终定位到答案。

下面通过 8 道 LeetCode 经典题目，帮助你掌握二分算法的写法与细节。

在开始刷题之前，先给出二分算法的两种通用模板，后续题目基本都是在这两个模板上变形。

模板一：查找精确值（循环条件 left <= right）

intbinarySearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target)returnmid;elseif(nums[mid]<target)left=mid+1;elseright=mid-1;}return-1;}

模板二：查找边界（循环条件 left < right）

// 找左边界：右区间的左边界intleftBound(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}returnleft;}// 找右边界：左区间的右边界intrightBound(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left+1)/2;if(nums[mid]>target)right=mid-1;elseleft=mid;}returnleft;}

注意：模板二求 mid 时，找左边界用left + (right - left) / 2（向下取整），找右边界用left + (right - left + 1) / 2（向上取整），否则可能死循环。

leetcode704 二分查找

https://leetcode.cn/problems/binary-search/

思路：

根据数组升序的特征，将数组划分为多个区域，进行查找。
注意循环条件是 left <= right，因为判断在循环内进行，当 left == right 时，当前元素还没有判断，因此需要取等。

代码实现：

classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=(left+right)/2;if(target<nums[mid])right=mid-1;elseif(target==nums[mid])returnmid;elseleft=mid+1;}return-1;}};

leetcode34 在数组中查找元素的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

思路：

以找左边界为例：（设 resLeft 为左边界）
区间 [0, resLeft - 1] 上元素均 < target，区间 [resLeft, n - 1] 上的元素均 >= target，找到了二段性。
考虑 mid 落的位置：
若 mid 落在 [left, resLeft - 1]，arr[mid] < target，目标不在这个区间，更新 left = mid + 1，继续在 [mid + 1, right] 找；
若 mid 落在 [resLeft, right]，arr[mid] >= target，目标在这个区间最左侧，更新 right = mid（因为 mid 可能是最终结果，不能舍去），继续在 [left, mid] 找。
同理找右边界。

代码实现：

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){if(nums.empty())return{-1,-1};intleft=0,right=nums.size()-1;intret1=-1,ret2=-1;//找左边界while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}if(nums[left]==target)ret1=left;//找右边界right=nums.size()-1;while(left<right){intmid=left+(right-left+1)/2;if(nums[mid]>target)right=mid-1;elseleft=mid;}if(nums[left]==target)ret2=left;return{ret1,ret2};}};

leetcode35 搜索插入位置

https://leetcode.cn/problems/search-insert-position/

思路：

设插入位置为 index，[left, index - 1] 区间上的元素都 < target，而 [index, right] 区间上的元素都 >= target，具有二段性，本质找的就是右区间的左边界，就回到了上一题的解法。
但要注意 target 可能大于全部元素，这种情况下，当循环走完，left = right = n - 1，若此时 nums[left] < target，说明要插入下一个位置。

代码实现：

classSolution{public:intsearchInsert(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}returnnums[left]<target?left+1:left;}};

leetcode69 X的平方根

https://leetcode.cn/problems/sqrtx/

思路：

设输出的值为 index，[left, index] 上值的平方 <= X，[index + 1, right] 上的值 > X，因此数组具有二段性，要找的是左区间的右边界，使用二分算法。
注意：
left 从 1 开始。
mid = left + (right - left + 1) / 2，因为若最终只有两个元素时，mid 若取左边那个，left = mid 会死循环。

代码实现：

classSolution{public:intmySqrt(intx){intleft=1,right=x;while(left<right){longlongmid=left+(right-left+1)/2;if(mid<=x/mid)left=mid;elseright=mid-1;}returnx==0?0:left;}};

leetcode852 山脉数组的峰顶索引

https://leetcode.cn/problems/peak-index-in-a-mountain-array/

思路：

设峰顶索引的下标为 index，在区间 [left, index - 1] 上的元素，特征是：后一个元素 > 当前元素；而在区间 [index, left] 上的元素，特征是：后一个元素 < 当前元素，因此具有二段性，可用二分算法，找右区间的左边界。

代码实现：

classSolution{public:intpeakIndexInMountainArray(vector<int>&arr){intleft=0,right=arr.size()-1;while(left<right){intmid=left+(right-left)/2;if(arr[mid]<arr[mid+1])left=mid+1;elseright=mid;}returnleft;}};

leetcode162 寻找峰值

https://leetcode.cn/problems/find-peak-element/

思路：

因为只需返回任意一个峰值即可，思路和上一题一样。
任取一点 i，与下一个点 i + 1，若 nums[i] > nums[i + 1]，说明左侧区域一定存在山峰（因为最左端为负无穷）；而若 nums[i] < nums[i + 1]，说明右侧区域一定存在山峰（因为最右端也为负无穷）。

代码实现：

classSolution{public:intfindPeakElement(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<nums[mid+1])left=mid+1;elseright=mid;}returnleft;}};

leetcode153 寻找旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

思路：

旋转后有两种情况，一段单调递增和两段单调递增，其中两段单调递增为常规情况。
注意到旋转后右单调区间中的右边界元素一定大于所有左区间中元素，因此可以将右单调区间右边界元素设为参考值 target。
设要找的最小元素的下标为 index，则在 [left, index - 1] 区间，各元素均 > target；在 [index, right] 区间，各元素均 >= target，因此具有二段性。
要找最小元素，即找右单调区间的左边界。

代码实现：

classSolution{public:intfindMin(vector<int>&nums){intleft=0,right=nums.size()-1;inttarget=nums[right];while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)right=mid;elseleft=mid+1;}returnnums[left];}};

剑指Offer53 0~n-1中缺失的数字

https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/

思路：

法一：哈希表；
法二：遍历查找；
法三：累加 0 ~ n-1，再减去数组中所有值。
法四：异或运算，与 0 ~ n - 1 全异或一遍，结果就是缺失的数字。
法五：二分算法
设缺失的数字应在的下标为 index，则在区间 [left, index - 1] 上有 下标 == 元素；
在区间 [index, right] 上有 元素值 == 下标 + 1。
因此具有二段性，找右区间的左边界。

代码实现：

classSolution{public:inttakeAttendance(vector<int>&records){intleft=0,right=records.size()-1;while(left<right){intmid=left+(right-left)/2;if(records[mid]==mid)left=mid+1;elseright=mid;}returnleft==records[left]?left+1:left;}};