1 时间复杂度

二分法查找的时间复杂度 T(n)=T(n/2)+O(1)所以T(n)=O(logn) 所有最坏的情况是logn,最好的情况是O(1).

2 代码实现

//二分法查找

private int binarySearchRank(int num, int[] array) { 
       int result = -1;   
       int start = 0;      
       int end = array.length-1;   
       while (start<end){ 
           if(array[start] == num){  
              result =  start; 
               break;    
        }         
     if(array[end] == num){     
           result =  end;   
             break;    
        }        
    int middle = (start+end)/2;   
         if(array[middle]>num){     
            end = middle;     
       }else  if(array[middle]<num){   
             start = middle;       
     }else {           
            result = middle;  
              break;        
    }         
   if(start+1==end){     
           result =  -1;        
        break;      
      }      
  }      
  return result;  
  }

3 代码分析

可能存在这样一种情况，当所要查找的数值的大小在数组的最大值与最小值之间，但是又不存在。这时候会进入死循环。比如 数组为 [1，3，7，9，10]，num为4，这时候循环到sart=3，end=7，array[temp]=5，这时候num>array[temp]会一直执行下去。使用这种情况直接返回-1.也就是start=end-1的时候还没有找到目标值。