查找算法：二分法，插值法的公式详解——菜鸟进阶的必经之路！！！

拼搏现实的明天。 2022-11-16 05:50 154阅读 0赞

### @查找算法：二分法与插值的详细分析 ###

*   *  1、简单的二分法查找
     *   *  1.1、算法分析
         *  1.2、画图分析
         *  1.3、代码实现1：递归法
         *  1.3、代码实现2：循环法
     *  2、二分微改版：插值查找
     *   *  2.1、算法分析
         *  2.2、额，这个图就不画了，和二分差不多
         *  2.3、代码实现(递归法，循环请参考二分法的思路)：
     *  3、总结

## 1、简单的二分法查找 ##

--------------------

### 1.1、算法分析 ###

二分法，顾名思义，就是对其进行折半分别在两边查找。两边再分别进行折半、查找，再折半、再查找，直到找到为止，或者整个数组都找不到这个值，应立即结束查找。

### 1.2、画图分析 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]

### 1.3、代码实现1：递归法 ###

/** * * @param arr 查询的数组 * @param value 查询的值 * @return 查询到的值的索引 */
    	public static int ef(int arr[], int value) { 
    		int left = 0;
    		int right = arr.length - 1;
    		int mid = 0;
    		while (left <= right) { 
    			
    			mid = (left + right) >> 1;
    
    			if (value > arr[mid]) { 
    				left = mid + 1;
    			} else if (value < arr[mid]) { 
    				right = mid - 1;
    			} else { 
    				return mid;
    			}
    		}
    		return -1;
    	}

### 1.3、代码实现2：循环法 ###

## 2、二分微改版：插值查找 ##

--------------------

### 2.1、算法分析 ###

相比于二分法的折半，插值就相当于折插值数，至于什么是折插值数，我们需要先了解一下它的公式：

*    
    
 *  **二分法：mid = (left + right) >> 1** (较简单，就不做过多的介绍了！！)
 *    
    
 *  \***插值法：mid = left + (value-arr\[left\]) \* (right - left) / (arr\[right\] - arr\[left\])**
 *    
    首先，在使用插值法之前，我们需要先了解插值法的 使用条件：必须是一个已排序的数组，这一点和二分法一样，但如果要体现其价值，则必须是一个已排序的连续分布均匀的数组，因为在这样的数组中，无论查哪一个元素，都只用一次就能查询到这个值。至于为什么只用了一次，我们还得回到其公式上面，为了便于理解，先假设有一个连续分布均匀的数组，接下来的说明皆围绕该例子  
                                                                **arr\[\] = \{1,2,3,4,5,6\};**  
    对于插值法的公式，我们根据其条件可以发现 (right - left) => (arr\[right\] - arr\[left\]),因为连续分布的特性，索引和元素的差值是成正比的， 如果连续分布的元素差值为1，则可以发现(right - left) =(arr\[right\] - arr\[left\])，所以，根据其正比例的关系，我们可以将公式化简为 ： **mid = left + value - arr\[left\]**，这样一来，我们就能很清晰的观察其规律了，left为左边界，value - arr\[left\]的结果为left到value索引处元素的差值， 以arr为例，假设我们要查找3这个元素，那么套用公式就是 mid = 0 + 3 - 1 = 2,而arr\[2\]刚好等于3，注意，上面的化简公式只是为了方便理解而推论的，只适用于连续排列差值为1的数组，对于其他分布的数组并不适用，还是用插值法的公式，对于其他分布的数组来说， (right - left) / (arr\[right\] - arr\[left\])的值就是该数组的分布比例， (value-arr\[left\]) 是要查找的值与左边界的差值，用该差值/分布比例，就能得到要查找的值value的索引，再用该索引 - 左边界，得到的值就是要查找的值的索引。

*  公式总结：mid = left + (value-arr\[left\]) \* (right - left) / (arr\[right\] - arr\[left\])
    
     *  **(right - left) / (arr\[right\] - arr\[left\])**：数组的比例关系
     *  **(value-arr\[left\])**：左边界元素(相当于0)到value的元素差值(通俗说就是从0到查找处元素的差值)
     *  **left**：当前的左边界(并非一直为0，如果一次查找不到左边界响应也会发生变化)

### 2.2、额，这个图就不画了，和二分差不多 ###

### 2.3、代码实现(递归法，循环请参考二分法的思路)： ###

public static int insertValSearch(int arr[],int left,int right,int value) { 
    		if(left>right ) { 
    			return -1;
    		}
    		System.out.println("aaa");
    		
    		//自适应：如果是一个连续的有序数组，那么可以自适应，只需要一次能查到
    		//如果是一个非连续的有序数组，那么只能适应两端，两端之内的值则和二分一样
    		int mid = left + (right-left)*(value-arr[left])/(arr[right]-arr[left]);
    // System.out.println(mid);
    // int mid = left + value - arr[left];
    		System.out.println(mid);
    		if(value>arr[mid]) { 
    			return insertValSearch(arr, mid+1, right, value);
    		}else if(value<arr[mid]) { 
    			return insertValSearch(arr, left, mid-1, value);
    		}else { 
    			return mid;
    		}
    	}

## 3、总结 ##

越努力，越幸运，The harder you work, the more luck you have.

关注笔笔一起努力吧ヾ(◍°∇°◍)ﾉﾞ！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]: /images/20221022/79543656756d4dd694f284e9a270dff8.png