二分查找

递归

int binarySearch(int a[], int low, int high, int target) {  
    if(low > high)  //边界检查
        return -1;  

    int middle = (low + high)/2;

    if(target == a[middle]) 
        return middle;  
     
    if(target < a[middle]) 
        return binarySearch(a, low, middle-1, target);  
    
    if(target > a[middle]) 
        return binarySearch(a, middle+1, high, target);  
    
}  

非递归

int binarySearch2(int a[],  int low, int high, int target) {  
    int middle; 

    while(low <= high) {  
        middle = (low + high)/2;  
        if(target == a[middle])   
            return middle;  
        else if(target < a[middle]) 
            high = middle - 1;  
        else 
            low = middle + 1;        
    }  

    return -1;  
}  

注意：
1，为防止溢出，mid=low + (high-low)/2
2，high=mid-1, low=mid+1, 这样才能保证遍历到区间内的每一个点。如果是最后为了保证区间长度为1，应写为：

    while(high-low>1) {  
        mid = (low + high)/2;  
        if()   
            return ;  
        else if() 
            high = mid;  
        else 
            low = mid;        
    }