关于二分法的个人见解

我会带着你远行 2022-12-23 11:22 69阅读 0赞

# 关于二分法的一些理解 #

一般而言,我们在使用二分法的时候通常定义一个`low`一个`high`然后去求`mid`,在此就出现了第一个问题:  
　　１.　如何保证在求取过程中不会出现数据的溢出?  
　　我们采用的方法是`(high-low)/2+low`,其与`(high+low)/2`得到的结果是一样的。  
　　２.　在进行二分检索的时候我们让`mid`指针偏向中间的左侧还是中间的右侧?  
　　在我个人看来,我通常认为偏左侧和偏右侧一样,对于偏左侧而言无非就是采用如下代码:

mid=(high-low)/2+low;
    	if(target<A[mid]) high=mid-1;
    	else if(target>A[mid]) low=mid+1;
    	else return;

对于偏右侧而言是采用如下代码:

mid=(high-low+1)/2+low;
    	if(target<A[mid]) high=mid-1;
    	else if(target>A[mid]) low=mid+1;
    	else return;

然而，在今天做leetcode上面的一个题目的时候，我发现并不是这样的。有时候找到目标之后还不知道当前已经找到目标,需要继续往下走一步才能知道我们已经找到目标了,如果我们仍然采用上述思想,那我们就需要另外一个变量去维护上一步的结果,但是如果我们采用下面两种算法就不需要额外的变量。  
对于中间偏右而言，只需要如下修改代码：

while(没有找到结果){
        
      		mid=(high-low+1)/2+low;
      		if(target<A[mid]) high=mid-1;
      		else low=mid;
      	}
      	return mid;

而对于中间偏左，我们则没有办法实现。其实，这种写法更加具有通用性，即使我们能够确定当前的`mid`不是我们要的结果,我们仍然可以把他赋值给`low`或者`high`,这样我们复杂度仍然为O(`n`log`n`)但是却更加具有普遍性。所以，进行而分检索的时候我们还是让`mid`处于中间偏右的位置更好。  
个人感觉：（在做一些其他算法的时候似乎也是在中间有两个数的时候选择右侧的似乎更好一些。）