JAVA数据结构与算法的学习——折半查找和插值插值

电玩女神 2021-10-24 03:42 342阅读 0赞

折半查找又称二分查找，前提是线性表中的记录必须是关键码有序（通常从小到大有序）

思路图解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 1]

实现代码：

public class Test {
    
    	static int Binary_search(int[] a, int key) {
    		int low; // 定义最低位下标
    		int high; // 定义最高位下标
    		int mid; // 中间位
    
    		low = 0;
    		high = a.length - 1;
    		int count = 0;
    		while (low <= high) {
    			mid = (low + high) / 2;
    			if (key < a[mid]) {
    				high = mid - 1;
    				count++;
    			} else if (key > a[mid]) {
    				low = mid + 1;
    				count++;
    			} else {
    				System.out.println("count=" + count);
    				return mid;
    			}
    		}
    		return -1;
    	}
    
    	public static void main(String[] args) {
    		int a[] = new int[1000];
    		int key = 3;
    		for (int i = 1; i < 1000; i++) {
    			a[i] = i;
    		}
    		System.out.println(a[Binary_search(a, key)]);
    	}
    
    }

输出结果：

count=9
    3

经过九次查找到目标值3

接下来是插值插值，**其最大的核心mid的计算改变了**

代码：

public class Test {
    
    	static int Binary_search(int[] a, int key) {
    		int low; // 定义最低位下标
    		int high; // 定义最高位下标
    		int mid; // 中间位
    
    		low = 0;
    		high = a.length - 1;
    		int count = 0;
    		while (low <= high) {
    			 mid = low+(high-low)*(key-a[low])/(a[high]-a[low]); //插值
    			if (key < a[mid]) {
    				high = mid - 1;
    				count++;
    			} else if (key > a[mid]) {
    				low = mid + 1;
    				count++;
    			} else {
    				System.out.println("count=" + count);
    				return mid;
    			}
    		}
    		return -1;
    	}
    
    	public static void main(String[] args) {
    		int a[] = new int[1000];
    		int key = 899;
    		for (int i = 1; i < 1000; i++) {
    			a[i] = i;
    			System.out.println(a[i]);
    		}
    		System.out.println(a[Binary_search(a, key)]);
    	}
    
    }

结果：

count=0
    899

直接就找到了，有点强

如果关键字分布比较均匀的查找表来说，插值查找算法的平均性能会比折半查找好得多，反之如果分布是比较极端不均匀的，用插值查找未必是很适合的选择。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70]: /images/20211023/78fa94a62c284827afa0ec5e51b97ff7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 1]: /images/20211023/3a7c4de0651f4b52b6be32fbd3d37c53.png