欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序表查找和折半查找

程序员文章站 2024-03-20 17:44:58
...

顺序查找
查找最好的情况是在第一个位置找到了,算法时间复杂度为O(1)
最坏的情况下在最后一个位置,需要n次比较,时间复杂度为O(n)
查不到,需要比较n+1次,时间复杂度为O(n+1)
关键字在任何一个位置上是相同的,所以平均查找次数为(n+1)/2
最终时间复杂度为O(n)

//n 数组长度,key 查找关键字,a为数组
int Sequential_Search(int key,int n,int *a)
{
    int i;
    for(i = 1;i<=n;i++)
    {
        if(a[i] == key)
            return i;
    }

    return 0;
}

改进的算法,设置哨兵,效率比第一个高

int Seqential_Search_new(int key,int n,int *a) 
{   
    int i;
    a[0] = key;/*设置哨兵,避免每次比较后都要判断查找位置是否越界*/
    i = n;/*循环从尾部开始*/
    while(a[i] != key)
    {
        i--;
    }
    return i;/*返回0 则查找失败*/
}

折半查找,又称二分查找
基本思想是在有序表中,取中间记录最为比较对象。若查找值与中间记录值相等,则查找成功;
否则小于中间值,则在左半区继续查找;大于中间值在右半区查找

int Binary_Search(int *a,int n,int key)
{
    int low,high,mid;
    low = 1;
    high = n;
    while(low <= high)
    {
        mid = (low + high)/2;

        if(key < a[mid])
            high = mid - 1;
        else if(key > a[mid])
            low = mid + 1;
        else 
            return mid;
    }
    return 0;
}