查找----二分查找法

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）。

补充：软件开发 , C语言 ,