算法技术手册 – 查找 – 顺序查找

顺序查找也叫线性查找,是最简单的查找算法。穷举法遍历每个元素,查找是否包含元素t。

平均、最坏性能O(N)

#include <stdio.h>

typedef int TYPE;

int search(TYPE* arr, int n, TYPE t)
{
    int i=0;
    for(i=0; i<n; i++)
    {   
        if(arr[i]==t)
        {   
            return 1;
        }   
    }   
    return 0;
}

int main()
{
    TYPE arr[8] = {-1,2,3,4,5,6,7,8};
    TYPE key = -10;

    printf("Is %d in array: %d\n", key, search(arr, sizeof(arr)/sizeof(TYPE), key));

    return 0;
}

如果目标元素t的分布是不均匀的,则有一些优化的方法。

  • 被找到的元素t有可能被再次找到:成功找到则移动到最前面。
  • 被找到的元素有更大可能性被找到:成功找到则向前移动一位(冒泡到前面),避免了上面方法中大量移动的耗时操作。且最终,反复被找到的元素会被冒泡到最前面。
  • 如果元素不会被多次查找到:成功找到则移动到最后。

Leave a Reply

Your email address will not be published. Required fields are marked *