彩票网站招代理广告怎么做,外贸网站 费用,福州百度分公司,数据库作业代做网站注#xff1a;本文同步发布于稀土掘金。
3 有序表查找
3.1 折半查找 折半查找#xff08;Binary Search#xff09;技术#xff0c;又称为二分查找#xff0c;它的前提是线性表中的记录必须是关键码有序#xff08;通常从小到大有序#xff09;#xff0c;线性表必须…注本文同步发布于稀土掘金。
3 有序表查找
3.1 折半查找 折半查找Binary Search技术又称为二分查找它的前提是线性表中的记录必须是关键码有序通常从小到大有序线性表必须采用顺序存储。 折半查找的基本思想是在有序表中取中间记录作为比较对象若给定值与中间记录的关键字相等则查找成功若给定值小于中间记录的关键字则在中间记录的左半区继续查找若给定值大于中间记录的关键字则在中间记录的右半区继续查找。不断重复上述过程直到查找成功或所有查找区域无记录查找失败为止。 代码有多种实现方式以下是示例
/*** Binary Search** author Korbin* date 2023-04-19 17:57:03**/
public class BinarySearchT extends ComparableT {/*** binary search* p* return index in data if searched, else return -1** param data array to search* param key key to search* return index of key in data* author Korbin* date 2023-04-19 18:30:33**/public int binarySearch(T[] data, T key) {int length data.length;int from 0;int to length - 1;// if key little than data[0] or key greater than data[length - 1], return -1, means search failedif (data[from].compareTo(key) 0 || data[to].compareTo(key) 0) {return -1;}int mid ((to - from) 1) / 2;while (from to) {// if data[mid] equals key, then return midif (data[mid].equals(key)) {return mid;}if (data[mid].compareTo(key) 0) {// if key greater than data[mid], then search from [mid 1, to]from Math.min(mid 1, length - 1);} else if (data[mid].compareTo(key) 0) {// if key little than data[mid], then search from [from, mid - 1]to Math.max(mid - 1, 0);}if (from to) {// if from equals to, then check if data[from] equals keyreturn (data[from].equals(key)) ? from : -1;}mid from ((to - from) 1) / 2;}return -1;}}3.2 插值查找 插值查找Interpolation Search是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法其核心在于插值公式 k e y − a [ f r o m ] a [ t o ] − a [ f l o w ] \frac {key-a[from]}{a[to]-a[flow]} a[to]−a[flow]key−a[from]。 从时间复杂度来看它也是O(logn)但对于表长较大而关键字又分布比较均匀的查找表来说插值查找的平均性能要比折半查找算法的性能要好很多。反之如果数组分布不均匀用插值查找未必有优势。 插值查找是在折半查找的基础上进行优化的在折半查找中计算mid的算法为 m i d f r o m 1 2 ( ( t o − f r o m ) 1 ) mid from \frac {1}{2}((to - from) 1) midfrom21((to−from)1) 在插值查找算法中则是 m i d f r o m k e y − a [ f r o m ] a [ t o ] − a [ f l o w ] ( ( t o − f r o m ) 1 ) mid from \frac {key-a[from]}{a[to]-a[flow]}((to - from) 1) midfroma[to]−a[flow]key−a[from]((to−from)1) 因此代码只作少量改动
/*** interpolation search* p* return index in data if searched, else return -1** param data array to search* param key key to search* return index of key in data* author Korbin* date 2023-04-19 18:30:33**/
public int interpolationSearch(int[] data, int key) {int length data.length;int from 0;int to length - 1;// if key little than data[0] or key greater than data[length - 1], return -1, means search failedif (data[from] key || data[to] key) {return -1;}int mid ((key - data[from]) / (data[to] - data[from])) / 2 * ((to - from) 1);while (from to) {// if data[mid] equals key, then return midif (data[mid] key) {return mid;}if (data[mid] key) {// if key greater than data[mid], then search from [mid 1, to]from Math.min(mid 1, length - 1);} else if (data[mid] key) {// if key little than data[mid], then search from [from, mid - 1]to Math.max(mid - 1, 0);}if (from to) {// if from equals to, then check if data[from] equals keyreturn (data[from] key) ? from : -1;}mid from ((key - data[from]) / (data[to] - data[from])) / 2 * ((to - from) 1);}return -1;
}调整一下mid的计算方式即可。
3.3 斐波那契查找 以下是一个斐波那契数组 斐波那契数组的特性是后一个元素的值等于前两个元素值的和即F[K]F[K-1]F[K-2]。此外F[K]/F[K1]无限接近于0.618。斐波那契查找法依据这一特性将数据分割成两部分并把F[K-1]-1作为mid值进行对比处理。 例如假设数组长度是88在斐波那契数组中的下标是6那么把数组分为两段长度分别是F[K-1]F[5]5F[K-2]F[4]3令midF[K-1]-15-14比较要查找的数值与被查找的数组A中下标为4的元素的大小。 在持续查找的过程中被查找的数组A因为是有序数组所以如果mid所对应的元素值大于要查找的数值时进行下一轮查找时则应到被查找数组的下半段去查找下半段数组长度是多少呢上文提到裴波那契数组的特性F[K]F[K-1]F[K-2]而斐波那契查找就是将数组分成两段前半段长度是F[K-2]后半段长度是F[K-1]因此当我们在后半段查找时后半段的数组长度是F[K-1]即新的KK-1接下来的mid计算方式仍然不变。 而这种情况下下标为mid以及其后的元素在下一轮查找时显然不可以再用于查找因此它们肯定会大于要查找的这个值因此我们设置一个变量high令其初始值为数组的长度在A[mid]大于要查找的数值时令highmid-1表示最多可以被查找的元素下标是high对应的元素值是A[high]。 而如果mid所对应的元素值小于要查找的数值时需要进行下一轮查找时因为前半段长度为F[K-2]因此新的KK-2而mid的计算方式不再是midF[K-1]-1而是“上一轮的mid”1F[K-1]-1我们设置一个变更low令其等于“上一轮的mid”1那么mid的计算方式就变成了midlowF[K-1]-1由于第一轮查找时没有“上一轮的mid”所以如果按照这个公式第一轮的low则为1这样可以保证mid的计算公式一直是midlowF[K-1]-1。 根据以上分析可知 (1) 变量mid表示使用数组中下标为mid的元素与要查找的数值进行比较 (2) 变量k表示被查找的数组长度在斐波那契数组中的位置 (3) 变量low表示从数组的下标为low的元素开始查找初始值为1当A[mid]被查找的元素时lowmid1同时置kk-2 (4) 变量high表示最多查到数组的下标为high的元素初始值为数组的最大下标当A[mid]被查找的元素时highmid-1同时置kk-1 现在我们来开始尝试假设有以下数组 我们需要从中找到数值59所在的位置。 首先初始化low1high数组的最大下标10同时定义一个斐波那契数组 然后第一次查找我们来找k已知数组长度为11在斐波那契数组f中并未找到10这个元素有两个选择 如果选择8即k6f[k]f[6]8假设我们要查找的是99会出现什么情况呢 (1) 第一轮midlowf[k-1]-11f[5]-115-15由于a[mid]要查找的数值因此新的kk-23新的lowmid1516 (2) 第二轮midlowf[k-1]-16f[2]-161-16由于a[mid]要查找的数值因此新的kk-20新的lowmid1617 (3) 第三轮midlowf[k-1]-17f[0-1]-1无法再继续而此时仍有a[7]~a[10] 如果选择13即k7f[k]f[7]13假设我们要查找的是99会出现什么情况呢 (1) 第一轮midlowf[k-1]-11f[6]-118-18a[8]99因此新的kk-24新的lowmid1819 (2) 第二轮midlowf[k-1]-19f[3]-193-111这时会发现11已经超过了a的最大下标10查找直接失败 (3) 此时我们进行一些调整将数组a的长度扩大到f[k]即13位并补齐后两位的值为f[10]即f[11]f[12]f[10]99这时再来查询就可以得到a[11]99找到99在数组a的下标为11的位置而由于原始的a最大下标为10因此直接返回10即可。 由此找到规则当数组长度在斐波那契数组中找不到对应元素时取与数组长度相邻但大于数组长度的那个元素的下标作为k同时将被查找的数组长度扩大到k并补齐后续元素值使其等于被查找的数组的最后一个元素值。 因此我们取k7此时数组a和f的结构如下所示 开始第一轮查找此时midlowf[k-1]-11f[6]-118-18a[8]7359因此highmid-18-17kk-17-66 第二轮查找midlowf[k-1]-11f[5]-15a[5]4759因此lowmid1516kk-26-24 第三轮查找midlowf[k-1]-16f[2]-161-16a[6]59得到查找结果返回查找值59所在的下标是6查找结束。 依据以上分析代码实现比较简单
import java.util.Arrays;/*** 斐波那契查找** author Korbin* date 2023-11-09 09:16:33**/
public class FibonacciSearch {/*** 定义一个斐波那契数组** param length 数组长度* return 斐波那契数组* author Korbin* date 2023-11-09 09:26:32**/private static int[] fibonacciArray(int length) {int[] array new int[length];array[0] 0;if (length 1) {return array;} else if (length 2) {array[1] 1;return array;} else {array[1] 1;for (int i 2; i length; i) {array[i] array[i - 1] array[i - 2];}return array;}}/*** 查找key在数组array中的下标找不到时返回-1** param array 被查找的数组* param key 要查找的key* return key在array中的下标* author Korbin* date 2023-11-09 09:28:51**/private static int fibonacciSearch(int[] array, int key) {int length array.length;// 如果被查找的数组只有一位则直接比较返回if (length 1) {if (array[0] key) {return 0;} else {return -1;}}// 因为是从下标为1的数组开始查找的因此先比较下标为0的元素if (array[0] key) {return 0;}int[] fibonacciArray fibonacciArray(length);// low初始为1int low 1;// high初始为length - 1int high length - 1;// 从斐波那契数组中找到kint k 0;for (int i 0; i length; i) {if (length fibonacciArray[i]) {k;}}// 如果被查找的数组长度小于k则扩充数组int[] newArray Arrays.copyOf(array, fibonacciArray[k]);if (fibonacciArray[k] length) {for (int i length; i fibonacciArray[k]; i) {newArray[i] array[length - 1];}}// 开始查找while (low high) {// 计算midint mid low fibonacciArray[k - 1] - 1;if (key newArray[mid]) {high mid - 1;k k - 1;} else if (key newArray[mid]) {low mid 1;k k - 2;} else {if (mid length) {return mid;} else {return length - 1;}}}return -1;}public static void main(String[] args) {int[] array new int[]{0, 1, 16, 24, 35, 47, 59, 62, 73, 87, 99};for (int j : array) {int index fibonacciSearch(array, j);System.out.println(元素 j 的下标是 index);}}}
