当前位置：首页 > news >正文

二分法（Binary Search）

news 2026/5/25 23:57:29

二分法（Binary Search）

一、算法基本原理

1.核心思想

二分法（Binary Search）是一种基于分治策略的高效搜索算法，其核心思想是：

利用有序性（单调性）前提
每次搜索区间对半划分
通过比较中间元素与目标值，排除一半不可能的区域。

2.数学原理

假设有序数组长度为n,每次比较后排除一半的元素：

第一次比较后剩余：n/2;
第二次比较后剩余：n/4
第k次比较后剩余：n/2^k

最坏情况需要满足：n/2^k=1
解得：k=log2^n

二、核心算法实现

1.基本二分查找（精准匹配）

#include<vector>#include<iostream>usingnamespacestd;//迭代实现intbinarySearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;//左闭右闭区间while(left<=right){//区间有效时继续intmid=left+(right-left)/2;//防溢出写法if(nums[mid]==target){returnmid;//找到目标}elseif(nums[mid]<target){left=mid+1;//目标在右半区}else{right=mid-1;//目标在左半区}}return-1;}//递归实现intbinarySearchRecursive(vector<int>&nums,inttarget,intleft,intright){if(left>right){return-1;//基准情况}intmid=left+(right-left)/2;if(nums[mid]==target){returnmid;}elseif(nums[mid]<target){returnbinarySearchRecursive(nums,target,mid+1,right);}else{returnbinarySearchRecursive(nums,target,left,mid-1);}}

2.边界处理技巧

// 三种常用区间写法intbinarySearchStyle1(vector<int>&nums,inttarget){// 风格1：左闭右闭 [left, right]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;}intbinarySearchStyle2(vector<int>&nums,inttarget){// 风格2：左闭右开 [left, right)intleft=0,right=nums.size();// 注意right初始值while(left<right){// 等号无意义intmid=left+(right-left)/2;if(nums[mid]==target)returnmid;elseif(nums[mid]<target)left=mid+1;elseright=mid;// 注意这里}return-1;}intbinarySearchStyle3(vector<int>&nums,inttarget){// 风格3：左开右开 (left, right)intleft=-1,right=nums.size();while(left+1<right){// 相邻时停止intmid=left+(right-left)/2;if(nums[mid]==target)returnmid;elseif(nums[mid]<target)left=mid;elseright=mid;}return-1;}

三、二分法模版与变体

1.查找第一个等于target的元素

intfindFirstEqual(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;intresult=-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]>=target){if(nums[mid]==target)result=mid;// 记录但不返回right=mid-1;// 继续向左寻找}else{left=mid+1;}}returnresult;}// 简洁版intfirstEqual(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]>=target){right=mid-1;}else{left=mid+1;}}// 检查边界和值if(left<nums.size()&&nums[left]==target){returnleft;}return-1;}

2.查找最后一个等于target的元素

intfindLastEqual(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;intresult=-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]<=target){if(nums[mid]==target)result=mid;left=mid+1;// 继续向右寻找}else{right=mid-1;}}returnresult;}

3.查找第一个大于等于target的元素

intlowerBound(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]>=target){right=mid-1;// 尝试更小的位置}else{left=mid+1;}}returnleft;// 注意：可能返回nums.size()表示所有元素都小于target}

4.查找第一个大于target的元素

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

四、应用场景分类

1.有序数组查找类

// 场景1：在有序数组中查找元素intsearchInSortedArray(vector<int>&nums,inttarget){returnbinarySearch(nums,target);}// 场景2：寻找峰值元素（任意峰值）intfindPeakElement(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]>nums[mid+1]){right=mid;// 峰值在左边或当前}else{left=mid+1;// 峰值在右边}}returnleft;}

2.旋转数组查找类

// 场景3：搜索旋转排序数组（无重复）intsearchInRotatedArray(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target)returnmid;// 判断哪边是有序的if(nums[left]<=nums[mid]){// 左半部分有序if(nums[left]<=target&&target<nums[mid]){right=mid-1;// 目标在有序的左半部分}else{left=mid+1;// 目标在右半部分}}else{// 右半部分有序if(nums[mid]<target&&target<=nums[right]){left=mid+1;// 目标在有序的右半部分}else{right=mid-1;// 目标在左半部分}}}return-1;}

3.二分答案类

// 场景4：求平方根（整数部分）intmySqrt(intx){if(x<=1)returnx;intleft=1,right=x;intresult=0;while(left<=right){intmid=left+(right-left)/2;if(mid<=x/mid){// 防溢出写法result=mid;// 记录可能的答案left=mid+1;// 尝试更大的数}else{right=mid-1;// 平方太大，尝试更小的数}}returnresult;}// 场景5：在D天内送达包裹的能力（最小化最大值问题）intshipWithinDays(vector<int>&weights,intD){// 确定二分边界intleft=*max_element(weights.begin(),weights.end());// 至少能运最重的包裹intright=accumulate(weights.begin(),weights.end(),0);// 一天运完所有while(left<right){intmid=left+(right-left)/2;if(canShip(weights,D,mid)){right=mid;// 能运完，尝试更小的运载能力}else{left=mid+1;// 不能运完，需要更大的运载能力}}returnleft;}boolcanShip(vector<int>&weights,intD,intcapacity){intdays=1;intcurrent=0;for(intweight:weights){if(current+weight>capacity){days++;current=0;if(days>D)returnfalse;}current+=weight;}returntrue;}

4.数学计算类

// 场景6：计算x的n次方根（浮点数二分）doublenthRoot(doublex,intn){if(x==0)return0;doubleleft=0,right=max(1.0,x);doubleeps=1e-12;// 精度要求while(right-left>eps){doublemid=left+(right-left)/2;doublepower=1.0;for(inti=0;i<n;i++){power*=mid;}if(power<x){left=mid;}else{right=mid;}}returnleft;}