二分查找你真的懂？

妖狐艹你老母 2023-02-21 09:31 1阅读 0赞

二分查找简直是简单的不能再简单的一个算法了， 很多人入门时几乎都是踩着二分查找的尸体入门的，那么这个算法你除了会用，思考过里边的一些细节吗？比如这个为什么这样设计? 那个为什么那样设计?接下来我就带你重新认识一下这个既熟悉又陌生的二分查找。  
  二分查找的大体思路，就是将一个**有范围限定的数\*\*\*\*比较次数降低**，不再像冒泡排序那样一个一个的比较，这个降低的比较次数是非常的大的，可以大大提升我们程序的效率。好了，这些估计你们都懂。  
先看一个运用二分法的程序：很明显这是一个求完全平方数的一个程序。

func isPerfectSquare(num int) bool { 
    	if num == 1 { 
    		return true
    	}
    	low, high := 2, num/2
    	for low <= high { 
    		mid := low + (high-low)>>1
    		result := mid * mid
    		if result == num { 
    			return true
    		} else if result > num { 
    			high = mid - 1
    		} else { 
    			low = mid + 1
    		}
    	}
    	return false
    }

1、你知道在计算mid时为什么大多数人要用**low + (high-low)>>1**这个公式吗？而不是直接用\*\*(low + high)/2\*\*这个公式吗？  
答案：（1）右移一位，相当于除以2，但右移的运算速度更快  
（2）若使用(low+high)/2求中间位置容易溢出  
2、你知道为什么low = mid + 1，high = mid - 1这样设计，而不是low = mid，high = mid这样设计吗？  
你可能会说，当然是为了进一步的减少比较次数了!  
我们先来看一个程序，这个程序的输出结果和上边这个程序的输出结果是相同的。

func isPerfectSquare(num int) bool { 
    	if num == 1 { 
    		return true
    	}
    	low, high := 2, num/2
    	for low <= high { 
    		mid := low + (high-low)>>1
    		result := mid * mid
    		if result == num { 
    			return true
    		} else if result > num { 
    			high = mid
    		} else { 
    			if(low == mid){ 
    				return false
    			}
    			low = mid
    		}
    	}
    	return false
    }

如果你仔细看完程序你会发现，在程序中，low = mid，high = mid，我是这样设计的。  
如果下边这个程序low = mid，high = mid这样设计，那么必须要有if(low == mid)\{return false\}这样一个条件，因为没有的话，某些数会造成死循环。所以，我觉得二分查找之所以这样设计low = mid + 1，high = mid - 1，第一是进一步的减少比较次数，第二个原因是防止由于low = mid，high = mid这样设计而忘写那个if判断条件出现死循环。