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

作者: veaxen 分类: 笔试面试 发布时间: 2017-07-27 13:43

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

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

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;
}

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

一条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.