查找--顺序查找

版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/f6ec95118574

定义
顺序查找又称为线性查找，其算法思路是从数组中的第一个（或最后一个）记录开始，将数组中元素逐个与需要查找的关键字进行比对，若发现有相等的，则查找成功；若始终未能相等，则查找失败。

Java实现

// 定义接口
interface Searcher {
    /**
     * 从数组array中查找关键字key,如果存在则返回该关键字在数组中任意出现的位置(不局限于首次或者末次之类的),否则返回-1
     */
    int search(int[] array, int key);
}

/**
 * 顺序表查找,时间复杂度为O(n)
 */
class LinearSearcher implements Searcher {
    @Override
    public int search(int[] array, int key) {
        int len = array.length;
        for (int i = 0; i < len; i++) {
            if (array[i] == key)
                return i;
        }
        return -1;
    }
}

LinearSearcher是标准的线性查找，这里有缺陷：在循环中每个循环实际上需要判断两次(一次是否相等,一次是否越界)，如何改进呢？其实就是设置“哨兵”：

/**
 * 优化的顺序表查找,时间复杂度O(n),但是比普通顺序表查找效率高
 */
class OptimizedLinearSearcher implements Searcher {

    // 相比单纯的线性查找每次for循环需要判断两次,这里设置关键字值(即哨兵)，可以让每次for循环只判断一次
    // 当数据量比较大时,如果单纯从线性查找角度看,优化后的线性搜索优势明显
    @Override
    public int search(int[] array, int key) {
        int len = array.length;
        if (len == 0) // array为空,返回-1
            return -1;
        if (array[0] == key)
            return 0;
        array[0] = key; // array[0]不是key,那么将key赋值给array[0],将array[0]作为哨兵
        // 这里"哨兵"也可以放在数组尾部
        int i = len - 1;
        while (array[i] != key) { // 每次循环少判断一个
            i--;
        }
        if (i == 0) // 从数组尾部一直查找到array[0]才找到,说明不存在
            return -1;
        return i;
    }
}

不论是线性查找还是改进后的线性查找，其时间复杂度都为O(n)