查找-折半查找（二分查找）-蒲公英云

查找-折半查找（二分查找）

折半查找

折半查找，也称为二分查找。其要求是数据是有序的，即表中元素按关键字有序。

比如有序表是递增有序的。首先取这表中的中间的数据与关键值（给定值key）比较的关系。若key>表的中间值，则说明key存在于表的中间值的右侧。因此，中间值右侧的区间又要取出中间值再与key比较，以此类推，直至查找成功或者区间缩小为0时还找不到就结束。

若key有与表中某区间的中间值相等，则说明查找成功。

若表的区间缩小为0时，仍然没有找到与key相匹配的值，就说明key不在表中。

特点：只适合用于顺序存储结构，而不适用于链式存储结构。表必须要求是有序表。

时间复杂度：

O(log2(n))

折半查找的基本思路：

优点：效率高，平均性能好

缺点：插入删除困难

代码：

(1)

#include<stdio.h>
#define MAXL 10
typedef struct
{
    int key;
}NodeType;
typedef NodeType SeqList[MAXL];
int BinSearch(SeqList r,int n,int k)
{
    int left=0,right=n-1,mid;
        printf("\n中间值：");
    while(left<=right)
    {
        mid=(left+right)/2;
            printf("%d  ",mid);
        if(r[mid].key==k)
        {
                return mid;
        }
        if(r[mid].key>k)
            right=mid-1;
        else
            left=mid+1;
    }
    return -1;
}
void main()
{
    SeqList r;
    int k=7;
    int a[10]={0,1,2,3,4,5,6,7,8,9},i,n=10;
    for(i=0;i<n;i++)
        r[i].key=a[i];
    printf("关键字序列：");
    for(i=0;i<n;i++)    
    {
        printf("%d  ",r[i].key);
    }
    if((i=BinSearch(r,n,k))!=-1)
        printf("\n元素%d的位置是%d\n",k,i);
    else
        printf("元素%d不在表中\n",k);
}

(2)

#include<stdio.h>
int BinSearch(int arr[],int n,int k)
{
    int left=0,right=n-1,mid;
        printf("\n中间值：");
    while(left<=right)
    {
        mid=(left+right)/2;
            printf("%d  ",mid);
        if(arr[mid]==k)
        {
                return mid;
        }
        if(arr[mid]>k)
            right=mid-1;
        else
            left=mid+1;
    }
    return -1;
}
void main()
{
    int k=7;
    int a[10]={0,1,2,3,4,5,6,7,8,9},i,n=10;
    printf("关键字序列：");
    for(i=0;i<n;i++)    
    {
        printf("%d  ",a[i]);
    }
    if((i=BinSearch(a,n,k))!=-1)
        printf("\n元素%d的位置是%d\n",k,i);
    else
        printf("元素%d不在表中\n",k);
}