查找-顺序查找-向日葵屋

查找-顺序查找

1.顺序查找定义

顺序查找(Sequential Search)又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查记录；如果直到最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

2.顺序表查找算法

/*顺序查找，a为数组,n为要查找的数组个数，key为要查找的关键字*/
int Sequential_Search(int *a,int n,int key)
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(a[i]==key)
        {
            return i;
        }
    }
    return 0;
}

上面这段代码非常简单，就是在数组a(元素值从下标1开始)中查看有没有关键字(key)，当你需要查找复杂表结构的记录时，只需要把数组a与关键字key定义成你需要的表结构和数据类型即可。

3.顺序表查找优化

上面的算法并非足够好，因为每次循环都需要对i是否越界，即是否小于等于n作判断。事实上，还可以有更好一点的办法，设置一个哨兵，可以不需要每次让i与n作比较。

/*有哨兵顺序查找*/
int Sequential_Search2(int *a,int n,int key)
{
    int i;
    a[0]=key;//设置a[0]为关键字值，我们称之为"哨兵"
    i=n;    //循环从数组尾部开始
    while(a[i]!=key)
    {
        i--;
    }
    return i;//返回0则说明查找失败
}

此时代码是从尾部开始查找，由于a[0]=key，也就是说，如果在a[i]中有key则返回i值，查找成功。否则一定在最终的a[0]处等于key，此时返回的是0，即说明a[1]~a[n]中没有关键字key，查找失败。

这种在查找方向的尽头放置”哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编程技巧。当然，”哨兵”也不一定就一定要在数组开始，也可以在末端。

4.顺序查找实现(Java)

实现的目录结构

顺序查找类

package com.red.sequence.search;
public class SequenceSearch {
    public int orderSearch(int[] arr, int key) {
        if(arr==null || arr.length<1 ) {
            return -1;
        }
        for(int i=0; i<arr.length; i++) {
            if(arr[i]==key) {
                return i;
            }
        }
        return -1;
    }
}

测试类

package com.red.sequence.search;
public class SequenceSearchTest {
    public static void main(String[] args) {
        SequenceSearch ss = new SequenceSearch();
        int[] arr = new int[]{
   1,16,24,35,47,59,62,73,88,99};
        int search = ss.orderSearch(arr, 62);
        System.out.println("key所在位置：" + search);
    }
}

输出结果

key所在位置：6

5.顺序查找复杂度

对于这种顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为O(1)，最坏的情况是在最后一个位置才找到，需要n次比较，时间复杂度为O(n)，当查找不成功时，需要n+1次比较，时间复杂度为O(n)。关键字在任何一位置的概率都是相同的，所以平均查找次数为(n+1)/2，所以最终时间复杂度为O(n)。