那些查找们

查找是算法入门的第二关，喜闻乐见，隆重登场

二分查找

对排好序的数组，效率相当不错，lnN搞定查找

代码实现

int bsearch(int a[],const int& x,int n){ 
//在从小到大排好序的a[n]，中查找值为x的元素
//找到则返回x在数组中的位置，否则返回-1
    int l=0,r=n-1;
    int mid;
    while(l<=r)
{ 
        mid=(l+r)/2;
        if(x==a[mid]) return mid;
        if(x>a[mid]) l=mid+1;
        else r=mid-1;
    }
    return -1;
}

二叉排序树查找

那如果没有排好序的数组呢，可以构建一个二叉排序树

代码实现(假设我们已经定义好了一个二叉排序树)

BiTree BSTsearch(BiTree T,int x){   
    if(!T)    
        return Null;    
    if(T->data.value == x)    
        return T;     
    if(T->data.value < x)      
        return BSTsearch(T->left,x);      
    else    
        return BSTsearch(T->right,x);  
}

参考

[1]wiki二叉查找树