查找----二分查找法

1、二分查找法

    二分查找法有一個很重要的前提條件：即待查找的序列必須是已經排好序的。

    假設元素序列是按升序排列，將序列中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將序列分成前、後兩個子序列，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子序列，否則進一步查找後一子序列。重復以上過程，直到找到滿足條件的記錄，查找成功，返回元素在序列中的索引，或直到子序列不存在為止，此時查找失敗，返回-1。

int find2(int *array,int n,int val) 
{ 
    if (n<=0) 
    { 
        return -1; 
    } 
 
    int begin=0,end=n-1,mid; 
    while(begin<=end)             
    { 
        mid=(begin+end)/2; 
        if (array[mid]==val) 
            return mid; 
        else if(array[mid]>val) 
            end=mid-1; 
        else 
            begin=mid+1; 
    } 
 
    return -1; 
} 
2、使用二分查找樹查找

    首先創建一顆二分查找樹，我們知道二分查找樹的特點是左子樹的值都比根節點小，右子樹的值都比根節點大，且二分查找樹的中序遍歷所得到的元素是排好序的。

[html] 
//二叉查找樹數據結構 
typedef struct Btree  
{ 
    int data; 
    Btree *left; 
    Btree *right; 
}*PBTree; 
 
//創建二叉查找樹，返回樹的根節點 
PBTree CreateBTree(int *array,int n) 
{ 
    PBTree root=new Btree; 
    root->data=array[0]; 
    root->left=NULL; 
    root->right=NULL; 
 
    PBTree current,back,pNew; 
    for (int i=1;i<n;i++) 
    { 
        pNew=new Btree; 
        pNew->data=array[i]; 
        pNew->left=pNew->right=NULL; 
        current=root; 
        while(current!=NULL)   //找到合適的插入位置 
        { 
            back=current; 
            if(current->data>array[i]) 
                current=current->left; 
            else 
                current=current->right; 
        } 
        if(back->data>array[i]) 
            back->left=pNew; 
        else 
            back->right=pNew; 
    } 
 
    return root; 
} 
 
//利用二叉查找樹進行遞歸查找 
bool find3(PBTree root,int val) 
{ 
    if (root==NULL) 
        return false; 
    if (root->data==val) 
        return true; 
    else if(root->data>val) 
        return find3(root->left,val); 
    else 
        return find3(root->right,val); 
} 
3、總結

    二分查找有非常嚴格的限制條件（序列必須是有序的）；

    而使用二分查找樹，則會自動創建出"有序樹"（中序遍歷得到的序列是有序的）；

    不考慮二叉查找樹的建立時間，二者的效率一樣，均為O（logn）。