二分查找的递归和非递归实现

如果面试题要求在已排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，我们都可以考虑尝试二分查找算法。

二分查找的递归实现代码：

int BinarySearch(int num,int array[],int low,int high)
{
    if(low > high) return -1;
    int mid = low + (high-low)/2;
    if(array[mid]>num) return BinarySearch(num,array,low,mid-1);
    else if(array[mid]<num) return BinarySearch(num,array,mid+1,high);
    else return mid;
}

二分查找的迭代实现代码：

int BinarySearch(int num,int array[],int len)
{
    int low = 0;
    int high = len-1;
    while(low <= high){
        int mid = low + (high - low)/2;
        if(array[mid] > num) high = mid - 1;
        else if(array[mid] < num) low = mid + 1;
        else return mid;
    }
    return -1;
}