二分查找

算法算法

创建时间:2019-02-26 11:05

阅读:

对分查找
1. 源码
2. 算法分析：

对分查找

源码

非递归方式：

int BinarySearch(const ElementType A[], ElementType X, int N)
{
    int low, mid, high, notfound;
    notfound = -1;
    low = 0;
    high = N - 1;
    while(low <= high){
        mid = (low + high) / 2;
        if(A[mid] > X){
            high = mid - 1;
        }else if(A[mid] < X){
            low = mid + 1;
        }else
            return mid;
    } 
    return notfound;
}

递归方式：

int BinarySearch(const ElementType A[], ElementType X, int low, int high)
{   
    mid = (low + high) / 2;

    if( A[mid] == X ){
        return mid;    
    }

    if( low >= high ){
        return -1;
    } else if( X < A[mid] ) {
        BinarySearch(A, X, low, mid-1);
    } else if( X > A[mid] ) {
        BinarySearch(A, X, mid+1, high)
    }
    return -1;
}

算法分析：

信息：

A数组本身就已经排好序
一共有N个数，每次折半查找

Key Mind:

分析循环的次数，逆向思维从0开始以2的幂次方查找，总共有N个数。设循环T次，表达式为2^T =N-1，则T=log(N-1)。所以运行时间为O(logN)。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 876208453@qq.com