常用查找算法

查找算法说明

查找定义：

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找算法分类：

1. 静态查找和动态查找

   注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2. 无序查找和有序查找

   无序查找：被查找数列有序无序均可

   有序查找：被查找数列必须为有序数列

平均查找长度（Average Search Length，ASL）：

需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi * Ci 的和。

• ​ Pi：查找表中第i个数据元素的概率。
• ​ Ci：找到第i个数据元素时已经比较过的次数。

顺序查找（Sequence Search）

基本思想

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

复杂度分析

查找成功时的平均查找长度为（假设每个数据元素的概率相等）： ASL = (1+2+3+…+n)/n = (n+1)/2

当查找不成功时，需要n+1次比较，时间复杂度为O(n)，所以，顺序查找的时间复杂度为O(n)。

代码实现

public static int SequenceSearch(int[] a, int value){
    int len = a.length;
    for(int i = 0; i < len; i++){
        if(a[i] == value) return i;
    }
    return -1;
}

public static int SequenceSearch(int[] a, int key) {
    int index = a.length - 1;
    //如果最后一个数是要找的，直接返回
    if (key == a[index])
        return index;
    //将最后一个数设置为哨兵
    a[index] = key;
    int i = 0;
    while (a[i++] != key);
    //若i == index + 1，说明没有查到，返回-1
    return i == index + 1 ? -1 : i - 1;
}

二分查找（Binary Search）

基本思想

1. 从已经排好序的数组或区间中取出中间位置的元素，判断该元素是否满足要搜索的条件，如果满足，停止搜索，程序结束。
2. 如果正中间的元素不满足条件，则从它两边的区域进行搜索。由于数组是排好序的，可以利用排除法，确定接下来应该从这两个区间中的哪一个去搜索。
3. 通过判断，如果发现真正要找的元素在左半区间的话，就继续在左半区间里进行二分搜索。反之，就在右半区间里进行二分搜索。

核心步骤：

1. 确定搜索的范围和区间
2. 取中间的数判断是否满足条件
3. 如果不满足条件，判定应该往哪个半边继续进行搜索

时间复杂度分析：

假设我们要对长度为 n 的数组进行二分搜索，T(n) 是执行时间函数，我们可以得到：
$T(n) = T(n/2) + 1$T(n)=T(n/2)+1
代入公式法得：a = 1，b = 2，f(n) = 1，因此：O(nlog(b)a) = O(n0) = 1 等于 O(f(n))，时间复杂度就是 O(nlog(b)alogn) = O(logn)。非常高效。因此也称为对数搜索，但要求待查找的数组或者区间是排好序的。

代码实现

递归解法：

public static int binarySearch(int[] nums, int target, int low, int high) {
	// 为了避免无限循环，先判断，如果起点位置大于终点位置，表明这是一个非法的区间
	if (low > high) {
        return -1;
    }
    // 取正中间那个数的下标 middle。
    int middle = low + (high - low) / 2;
    // 判断一下正中间的那个数是不是要找的目标数 target，是，就返回下标 middle。    
    if (nums[middle] == target) {
        return middle;
    }
    // 如果发现目标数在左边，就递归地从左半边进行二分搜索。
    // 否则从右半边递归地进行二分搜索
    if (target < nums[middle]) {
        return binarySearch(nums, target, low, middle - 1);
    } else {
        return binarySearch(nums, target, middle + 1, high);
    }
}

• 在计算 middle 下标的时候，不能简单地用 (low + hight) / 2，可能会导致溢出。
• 在取左半边以及右半边的区间时，左半边是 [low, middle - 1]，右半边是 [middle + 1, high]，这是两个闭区间。因为已经确定了 middle 那个点不是我们要找的，就没有必要再把它加入到左、右半边了。
• 对于一个长度为奇数的数组，例如：{1, 2, 3, 4, 5}，按照 low + (high - low) / 2 来计算，middle 就是正中间的那个位置，对于一个长度为偶数的数组，例如 {1, 2, 3, 4}，middle 就是正中间靠左边的一个位置。

非递归解法：

public static int binarySearch(int[] nums, int target, int low, int high) {
    // 在 while 循环里，判断搜索的区间范围是否有效
    while (low <= high) {
        // 计算正中间的数的下标
        int middle = low + (high - low) / 2;
        // 判断正中间的那个数是不是要找的目标数 target。如果是，就返回下标 middle
    	if (nums[middle] == target) {
        	return middle;
    	}
        // 如果发现目标数在左边，调整搜索区间的终点为 middle - 1；
        //否则，调整搜索区间的起点为 middle + 1
        if (target < nums[middle]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    // 如果超出了搜索区间，表明无法找到目标数，返回 -1  
    return -1;
}

插值查找（Insert Search）

基本思想

• 差值查找算法是对二分查找（折半查找）的一个优化
• 二分查找算法选取的是中间位置：mid = (low + high)/2
• 插值查找算法选取的是自适应mid位置开始查找: mid= low + (key - a[low])(high - low)/(a[high] - a[low])

使用场景

• 插值查找算法通过上面计算的mid，可以判断要查找的位置大概在哪里，对于表较长，且关键字分布比较均匀时候，查找比较快。
• 关键字分布不均匀的情况下，该方法不一定比折半查找要好

时间复杂度分析

如果元素均匀分布，则O(log2n)，在最坏的情况下可能需要 O(n)。

代码实现

递归实现：

public static int insertSearch(int[] nums, int target, int low, int high) {
	// 为了避免无限循环，先判断，如果起点位置大于终点位置，表明这是一个非法的区间
	if (low > high) {
        return -1;
    }
    
    // 二分查找
    //int middle = low + (high - low) / 2;
    // 插值查找
  	int middle = low + (high - low)*(target - nums[low])/(nums[high] - nums[low]);
    
    // 判断一下是不是要找的目标数 target，是，就返回下标 middle。    
    if (nums[middle] == target) {
        return middle;
    }
    // 如果发现目标数在左边，就递归地从左半边进行插值查找
    // 否则从右半边递归地进行插值查找
    if (target < nums[middle]) {
        return insertSearch(nums, target, low, middle - 1);
    } else {
        return insertSearch(nums, target, middle + 1, high);
    }
}

非递归解法：

public static int binarySearch(int[] nums, int target, int low, int high) {
    // 在 while 循环里，判断搜索的区间范围是否有效
    while (low <= high) {
         // 二分查找
    	//int middle = low + (high - low) / 2;
    	// 插值查找
  		int middle = low + (high - low)*(target - nums[low])/(nums[high] - nums[low]);
        // 判断一下是不是要找的目标数 target，是，就返回下标 middle
    	if (nums[middle] == target) {
        	return middle;
    	}
        // 如果发现目标数在左边，调整搜索区间的终点为 middle - 1；
        //否则，调整搜索区间的起点为 middle + 1
        if (target < nums[middle]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    // 如果超出了搜索区间，表明无法找到目标数，返回 -1  
    return -1;
}