二分查找

二分查找 O(logn)

递归方法
int binarySearch1(int a[] , int low , int high , int findNum)
{    
      if (low > high)        
          return -1;   

      int mid = ( high - low ) / 2 + low;       

      if (a[mid] > findNum)          
            return binarySearch1(a, low, mid - 1, findNum);        
      else if (a[mid] < findNum)            
            return binarySearch1(a, mid + 1, high, findNum);                    
      else            
            return mid;   
    
}

非递归方法
int binarySearch2(int a[] , int low , int high , int findNum)
{    
       int mid; 
       while (low <= high)
      {
            mid =  ( high - low ) / 2 + low;   //此处一定要放在while里面
            if (a[mid] < findNum)           
                low = mid + 1;        
            else if (a[mid] > findNum)            
                high = mid - 1;       
             else           
                return mid;    
    }       
    return  -1;
}

代码中有两点值得注意：

1. 中间值的写法mid = ( high - low ) / 2 + low而不要写成（high+low）/ 2
   因为当搜索到最右边部分时，high+low有可能会是一个非常大的一个值，造成溢出，程序崩溃。

2. 非递归方法mid的定义放在while外面，如果放在while里，会重复分配内存。