二分查找_二分查找最坏情况下比较次数

二分查找
===================================================
1、原理
将数组以中间值为中心，一分为二；

要找的值--等于中间值则直接返回；小于中间值，则从中间值左边找；大于中间值，则从中间值右边找；

循环直到找到要找的值为止。

前提:二分查找的前提是需要查找的数组必须是已排序的，我们这里的实现默认为升序。

2、java代码实现

可以用循环和递归两种方式实现。

/**
 * 二分查找
 */  
public class BinarySearch {  
      
    /**
     * 循环二分查找，返回第一次出现该值的位置
     * @param sortedData    已排序的数组
     * @param findValue     需要找的值
     * @return              值在数组中的位置，从0开始。找不到返回-1
     */  
    public static int searchLoop(int[] sortedData, int findValue){
        int start = 0;  
        int end = sortedData.length - 1;  
        while(start<=end && (start<=sortedData.length-1) && (end<=sortedData.length-1)){
            int middleIndex = (start+end) >> 1;        //中间位置,相当于(start+end)/2  
            int middleValue = sortedData[middleIndex]; //中间值
            if(findValue == middleValue){
                return middleIndex; //等于中值,直接返回  
            }else if(findValue < middleValue){      
                //小于中值时在中值前面找：start还是0，end改为中间值的前一个middleIndex - 1
                end = middleIndex - 1;
            }else{  
                //大于中值在中值后面找：end还是sortedDate.length-1，start为中间值的后一个moddleIndex+1
            	start = middleIndex + 1; 
            } 
        } 
        return -1; //找不到,返回-1 
    } 
    
    /**
     * 递归二分查找，返回第一次出现该值的位置 
     * @param sortedData 已排序的数组
     * @param findValue 需要找的值 
     * @return 值在数组中的位置，从0开始。找不到返回-1 
     */ 
    public static int searchRecursive(int[] sortedData, int findValue, int start, int end){ 
    	if(start <= end){ 
    		int middleindex = (start+end) >> 1; //中间位置,相当于(start+end)/2
    	    int middleValue = sortedData[middleindex]; //中间值 
    	    if(findValue == middleValue){ 
    	    	return middleindex; //等于中值直接返回
    	    }else if(findValue < middleValue){ //小于中值时在中值前面找 
    	    	return searchRecursive(sortedData,findValue,start,middleindex-1); 
    	    }else{ //大于中值在中值后面找
    	    	return searchRecursive(sortedData,findValue,middleindex+1,end); 
    	    } 
    	} 
    	return -1; 
    } 
    
    /** 
     * test 
     * @param args 
     */ 
    public static void main(String[] args) { 
    	int[] sortedData = {1,2,3,4,5,6,6,7,8,8,9,10}; 
    	//1.循环二分法查找 
    	int pos1 = searchLoop(sortedData, 12); 
    	System.out.println("循环二分法查找:" + pos1); 
    	
    	//2.递归二分法查找  
    	int pos2 = searchRecursive(sortedData, 12, 0, sortedData.length-1); 
    	System.out.println("递归二分法查找:" + pos2); 
    } 
	    
}
 

3、时间复杂度

比如：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2^k取整后>=1，即令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)

(--更好理解)假设其数组长度为n，经过m次二分查找到结果（即只剩下一个元素），则：n/(2^m) = 1（即n=m^2）。

其算法复杂度为o(log(n))

最大查找次数:

二分查找因为每次都是从中间点开始查找，所以最大查找次数（最坏情况）是目标元素存在于最边缘的情况。比如1~9，最坏情况就是1或者9，当然4,6这种也算是边缘（中心的边缘）。

所以不难发现：
最多比较1次的串长是1
最多比较2次的串长是2-3
3是4-7
4是8-15
x是2^(x-1)-2^x-1

最坏情况下次数：logN+1（logN向下取整