顺序查找

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n);
所以，顺序查找的时间复杂度为O(n)。

Python实现

def direct_search(array, dest_val):
    if not array:
        return '目标数组不存在，无法进行查找'
    if not dest_val:
        return '目标数据不存在，无法进行查找'

    for index, value in enumerate(array):
        if value == dest_val:
            return '目标数据第一次出现在目标数组的{}位'.format(str(index + 1))
    else:
        return '目标数据在目标数组中不存在'


dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = direct_search([], 3)
print(result)

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = direct_search(dest, 3)
print(result)

C语言实现

#include<stdio.h>


//直接顺序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}


int main()
{
    int a[] = {5, 2, 7, 4, 8, 1, 6, 3};
    int dest_val = 3;
    result = SequenceSearch(a, dest_val);
    if (result == -1)
        printf("数据不存在与数组中")
    else
        printf("目标数据第一次出现在 %d 位置上", result+1)


    return 0;
}