你真的会二分法吗?

前言:
二分法作为基础算法,几乎是每个程序员(甚至是非程序员都应该掌握的技能),然而,你真的完全了解二分法吗?二分法总体上有三种。不多说,直接上代码。

方法1

int binarySearch(vector<int>& nums,int target)
{
	  int left=0,right=nums.size()-1;
	  while(left<=right)
	  {
		    int mid=left+(right -left)>>1;
		    if(nums[mid]==target)
		    	return mid; 
		    else if(nums[mid]<target)
		    	left=mid+1; 
		    else
		    	right=mid-1; 
	  }
	  return -1;
}

方法一特点:
直接比较mid与target
起始条件:left=0,right=nums.size()-1
循环条件:left<=right
向左缩小:left=mid-1
向右缩小:right=mid+1
循环结束时:left==right+1

方法二:

int binarySearch(vector<int>& nums,int target)
{
	  int left=0,right=nums.size();
	  while(left<right)
	  {
		    int mid=left+(right -left)>>1;
		    if(nums[mid]==target)
		    	return mid; 
		    else if(nums[mid]<target)
		    	left=mid+1; 
		    else
		    	right=mid; 
	  }
	  if(left!=nums.size()&&nums[left]==target)
	  	return left;
	  return -1;
}

方法二特点:
比较mid+1位置上的元素与target
起始条件:left=0,right=nums.size()
循环条件:left<right
向左缩小:left=mid-1
向右缩小:right=mid
循环结束时:left==right

方法三

int binarySearch(vector<int>& nums,int target)
{
	  int left=0,right=nums.size()-1;
	  while(left+1<right)
	  {
		    int mid=left+(right -left)>>1;
		    if(nums[mid]==target)
		    	return mid; 
		    else if(nums[mid]<target)
		    	left=mid; 
		    else
		    	right=mid; 
	  }
	  if(nums[left]==target) 
	  	return left;
      if(nums[right]==target) 
      	return right;
	  return -1;
}

方法三特点:
比较mid-1,mid+1位置上的元素与target
起始条件:left=0,right=nums.size()-1
循环条件:left<right
向左缩小:left=mid
向右缩小:right=mid
循环结束时:left+1==right

总结:

比较方法 起始条件 循环条件 向左缩小 向右缩小 循环结束时
方法一 比较mid位置上的元素与target left=0,right=nums.size()-1 left<=right left=mid-1 right=mid+1 left==right+1
方法二 比较mid+1位置上的元素与target left=0,right=nums.size() left<right left=mid-1 right=mid left==right
方法三 比较mid-1,mid+1位置上的元素与target left=0,right=nums.size()-1 left<right left=mid right=mid left+1==right

你真的会二分法吗?

上一篇:冬季实战营学习报告


下一篇:MYSQL性能调优04_连接器、查询缓存、分析器、优化器、执行器、一图详解MYSQL底层工作原理(一)