本网站维护升级,楚天网站建设合同,辽宁建设工程人才网,wordpress做seo查找算法介绍 在java中#xff0c;我们常用的查找有四种: 顺序(线性)查找 二分查找/折半查找 插值查找斐波那契查找1)线性查找算法 示例#xff1a; 有一个数列#xff1a; {1,8, 10, 89, 1000, 1234} #xff0c;判断数列中是否包含此名称【顺序查找】 要求: 如果找到了我们常用的查找有四种: 顺序(线性)查找 二分查找/折半查找 插值查找斐波那契查找1)线性查找算法 示例 有一个数列 {1,8, 10, 89, 1000, 1234} 判断数列中是否包含此名称【顺序查找】 要求: 如果找到了就提示找到并给出下标值。 思路将数列遍历匹配就是用for循坏遍历if匹配数据找到下标值输出。 1 public class SeqSearch {2 3 public static void main(String[] args) {4 int arr[] { 1, 9, 11, -1, 34, 89 };// 没有顺序的数组5 int index seqSearch(arr, -11);6 if(index -1) {7 System.out.println(没有找到到);8 } else {9 System.out.println(找到下标为 index);
10 }
11 }
12
13 /**
14 * 这里我们实现的线性查找是找到一个满足条件的值就返回
15 * param arr
16 * param value
17 * return
18 */
19 public static int seqSearch(int[] arr, int value) {
20 // 线性查找是逐一比对发现有相同值就返回下标
21 for (int i 0; i arr.length; i) {
22 if(arr[i] value) {
23 return i;
24 }
25 }
26 return -1;
27 }
28
29 } 代码 2)二分查找算法 示例 请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} 输入一个数看看该数组是否存在此数并且求出下标如果没有就提示没有这个数。 思路 1 public static void main(String[] args) {2 //int arr[] { 1, 8, 10, 89,1000,1000, 1234 };3 int arr[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };4 5 6 //7 int resIndex binarySearch(arr, 0, arr.length - 1, 1000);8 System.out.println(resIndex resIndex);9
10 //ListInteger resIndexList binarySearch2(arr, 0, arr.length - 1, 1);
11 //System.out.println(resIndexList resIndexList);
12 }
13
14 // 二分查找算法
15 /**
16 *
17 * param arr
18 * 数组
19 * param left
20 * 左边的索引
21 * param right
22 * 右边的索引
23 * param findVal
24 * 要查找的值
25 * return 如果找到就返回下标如果没有找到就返回 -1
26 */
27 public static int binarySearch(int[] arr, int left, int right, int findVal) {
28
29
30 // 当 left right 时说明递归整个数组但是没有找到
31 if (left right) {
32 return -1;
33 }
34 int mid (left right) / 2;
35 int midVal arr[mid];
36
37 if (findVal midVal) { // 向 右递归
38 return binarySearch(arr, mid 1, right, findVal);
39 } else if (findVal midVal) { // 向左递归
40 return binarySearch(arr, left, mid - 1, findVal);
41 } else {
42
43 return mid;
44 }
45
46 } 代码 拓展 当一个有序数组中有多个相同的数值时如何将所有的数值都查找到比如这里的 1000{1,8, 10, 89, 1000, 10001234} 要查找出该数列中1000的下标又怎么找出呢 思路 1. 在找到mid 索引值不要马上返回2. 向mid 索引值的左边扫描将所有满足 1000 的元素的下标加入到集合ArrayList3. 向mid 索引值的右边扫描将所有满足 1000 的元素的下标加入到集合ArrayList4. 将Arraylist返回 1 public static void main(String[] args) {2 //int arr[] { 1, 8, 10, 89,1000,1000, 1234 };3 int arr[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };4 5 6 //7 // int resIndex binarySearch(arr, 0, arr.length - 1, 1000);8 // System.out.println(resIndex resIndex);9 10 ListInteger resIndexList binarySearch2(arr, 0, arr.length - 1, 1);11 System.out.println(resIndexList resIndexList);12 }13 14 // 二分查找算法15 /**16 * 17 * param arr18 * 数组19 * param left20 * 左边的索引21 * param right22 * 右边的索引23 * param findVal24 * 要查找的值25 * return 如果找到就返回下标如果没有找到就返回 -126 */27 public static int binarySearch(int[] arr, int left, int right, int findVal) {28 29 30 // 当 left right 时说明递归整个数组但是没有找到31 if (left right) {32 return -1;33 }34 int mid (left right) / 2;35 int midVal arr[mid];36 37 if (findVal midVal) { // 向 右递归38 return binarySearch(arr, mid 1, right, findVal);39 } else if (findVal midVal) { // 向左递归40 return binarySearch(arr, left, mid - 1, findVal);41 } else {42 43 return mid;44 }45 46 }47 48 49 /*50 * {1,8, 10, 89, 1000, 10001234} 当一个有序数组中51 * 有多个相同的数值时如何将所有的数值都查找到比如这里的 100052 * 53 * 思路分析54 * 1. 在找到mid 索引值不要马上返回55 * 2. 向mid 索引值的左边扫描将所有满足 1000 的元素的下标加入到集合ArrayList56 * 3. 向mid 索引值的右边扫描将所有满足 1000 的元素的下标加入到集合ArrayList57 * 4. 将Arraylist返回58 */59 60 public static ListInteger binarySearch2(int[] arr, int left, int right, int findVal) {61 62 System.out.println(hello~);63 // 当 left right 时说明递归整个数组但是没有找到64 if (left right) {65 return new ArrayListInteger();66 }67 int mid (left right) / 2;68 int midVal arr[mid];69 70 if (findVal midVal) { // 向 右递归71 return binarySearch2(arr, mid 1, right, findVal);72 } else if (findVal midVal) { // 向左递归73 return binarySearch2(arr, left, mid - 1, findVal);74 } else {75 // * 思路分析76 // * 1. 在找到mid 索引值不要马上返回77 // * 2. 向mid 索引值的左边扫描将所有满足 1000 的元素的下标加入到集合ArrayList78 // * 3. 向mid 索引值的右边扫描将所有满足 1000 的元素的下标加入到集合ArrayList79 // * 4. 将Arraylist返回80 81 ListInteger resIndexlist new ArrayListInteger();82 //向mid 索引值的左边扫描将所有满足 1000 的元素的下标加入到集合ArrayList83 int temp mid - 1;84 while(true) {85 if (temp 0 || arr[temp] ! findVal) {//退出86 break;87 }88 //否则就temp 放入到 resIndexlist89 resIndexlist.add(temp);90 temp - 1; //temp左移91 }92 resIndexlist.add(mid); //93 94 //向mid 索引值的右边扫描将所有满足 1000 的元素的下标加入到集合ArrayList95 temp mid 1;96 while(true) {97 if (temp arr.length - 1 || arr[temp] ! findVal) {//退出98 break;99 }
100 //否则就temp 放入到 resIndexlist
101 resIndexlist.add(temp);
102 temp 1; //temp右移
103 }
104
105 return resIndexlist;
106 }
107
108 } 代码 3)插值查找 插值查找原理介绍: 1.插值查找算法类似于二分查找不同的是插值查找每次从自适应mid处开始查找。 2.将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right. key 就是前面我们讲的 findVal 3.int mid low (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/*插值索引*/ 对应前面的代码公式 int mid left (right – left) * (findVal – arr[left]) / (arr[right] – arr[left]) 举例说明插值查找算法 1-100 的数组 1 public static void main(String[] args) {2 3 // int [] arr new int[100];4 // for(int i 0; i 100; i) {5 // arr[i] i 1;6 // }7 8 int arr[] { 1, 8, 10, 89,1000,1000, 1234 };9
10 int index insertValueSearch(arr, 0, arr.length - 1, 1234);
11 //int index binarySearch(arr, 0, arr.length, 1);
12 System.out.println(index index);
13
14 //System.out.println(Arrays.toString(arr));
15 }
16
17 public static int binarySearch(int[] arr, int left, int right, int findVal) {
18 System.out.println(二分查找被调用~);
19 // 当 left right 时说明递归整个数组但是没有找到
20 if (left right) {
21 return -1;
22 }
23 int mid (left right) / 2;
24 int midVal arr[mid];
25
26 if (findVal midVal) { // 向 右递归
27 return binarySearch(arr, mid 1, right, findVal);
28 } else if (findVal midVal) { // 向左递归
29 return binarySearch(arr, left, mid - 1, findVal);
30 } else {
31
32 return mid;
33 }
34
35 }
36
37 //编写插值查找算法
38 //说明插值查找算法也要求数组是有序的
39 /**
40 *
41 * param arr 数组
42 * param left 左边索引
43 * param right 右边索引
44 * param findVal 查找值
45 * return 如果找到就返回对应的下标如果没有找到返回-1
46 */
47 public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
48
49 System.out.println(插值查找次数~~);
50
51 //注意findVal arr[0] 和 findVal arr[arr.length - 1] 必须需要
52 //否则我们得到的 mid 可能越界
53 if (left right || findVal arr[0] || findVal arr[arr.length - 1]) {
54 return -1;
55 }
56
57 // 求出mid, 自适应
58 int mid left (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
59 int midVal arr[mid];
60 if (findVal midVal) { // 说明应该向右边递归
61 return insertValueSearch(arr, mid 1, right, findVal);
62 } else if (findVal midVal) { // 说明向左递归查找
63 return insertValueSearch(arr, left, mid - 1, findVal);
64 } else {
65 return mid;
66 }
67
68 } 代码 插值查找注意事项 1.对于数据量较大关键字分布比较均匀的查找表来说采用插值查找, 速度较快. 2.关键字分布不均匀的情况下该方法不一定比折半查找要好 4)斐波那契(黄金分割法)查找算法 斐波那契(黄金分割法)查找基本介绍: 1.黄金分割点是指把一条线段分割为两部分使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽因此称为黄金分割也称为中外比。这是一个神奇的数字会带来意向不大的效果。 2.斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例无限接近 黄金分割值0.618 斐波那契(黄金分割法)原理: 斐波那契查找原理与前两种相似仅仅改变了中间结点mid的位置mid不再是中间或插值得到而是位于黄金分割点附近即midlowF(k-1)-1 F代表斐波那契数列如下图所示 对F(k-1)-1的理解 1.由斐波那契数列 F[k]F[k-1]F[k-2] 的性质可以得到 F[k]-1F[k-1]-1F[k-2]-11 。该式说明只要顺序表的长度为F[k]-1则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段即如上图所示。从而中间位置为midlowF(k-1)-1 2.类似的每一子段也可以用相同的方式分割 3.但顺序表长度n不一定刚好等于F[k]-1所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可由以下代码得到,顺序表长度增加后新增的位置从n1到F[k]-1位置都赋为n位置的值即可。 斐波那契查找应用案例 请对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} 输入一个数看看该数组是否存在此数并且求出下标如果没有就提示没有这个数。 1 public static int maxSize 20;2 public static void main(String[] args) {3 int [] arr {1,8, 10, 89, 1000, 1234};4 5 System.out.println(index fibSearch(arr, 189));// 06 7 }8 9 //因为后面我们midlowF(k-1)-1需要使用到斐波那契数列因此我们需要先获取到一个斐波那契数列
10 //非递归方法得到一个斐波那契数列
11 public static int[] fib() {
12 int[] f new int[maxSize];
13 f[0] 1;
14 f[1] 1;
15 for (int i 2; i maxSize; i) {
16 f[i] f[i - 1] f[i - 2];
17 }
18 return f;
19 }
20
21 //编写斐波那契查找算法
22 //使用非递归的方式编写算法
23 /**
24 *
25 * param a 数组
26 * param key 我们需要查找的关键码(值)
27 * return 返回对应的下标如果没有-1
28 */
29 public static int fibSearch(int[] a, int key) {
30 int low 0;
31 int high a.length - 1;
32 int k 0; //表示斐波那契分割数值的下标
33 int mid 0; //存放mid值
34 int f[] fib(); //获取到斐波那契数列
35 //获取到斐波那契分割数值的下标
36 while(high f[k] - 1) {
37 k;
38 }
39 //因为 f[k] 值 可能大于 a 的 长度因此我们需要使用Arrays类构造一个新的数组并指向temp[]
40 //不足的部分会使用0填充
41 int[] temp Arrays.copyOf(a, f[k]);
42 //实际上需求使用a数组最后的数填充 temp
43 //举例:
44 //temp {1,8, 10, 89, 1000, 1234, 0, 0} {1,8, 10, 89, 1000, 1234, 1234, 1234,}
45 for(int i high 1; i temp.length; i) {
46 temp[i] a[high];
47 }
48
49 // 使用while来循环处理找到我们的数 key
50 while (low high) { // 只要这个条件满足就可以找
51 mid low f[k - 1] - 1;
52 if(key temp[mid]) { //我们应该继续向数组的前面查找(左边)
53 high mid - 1;
54 //为甚是 k--
55 //说明
56 //1. 全部元素 前面的元素 后边元素
57 //2. f[k] f[k-1] f[k-2]
58 //因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] f[k-2] f[k-3]
59 //即 在 f[k-1] 的前面继续查找 k--
60 //即下次循环 mid f[k-1-1]-1
61 k--;
62 } else if ( key temp[mid]) { // 我们应该继续向数组的后面查找(右边)
63 low mid 1;
64 //为什么是k -2
65 //说明
66 //1. 全部元素 前面的元素 后边元素
67 //2. f[k] f[k-1] f[k-2]
68 //3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] f[k-3] f[k-4]
69 //4. 即在f[k-2] 的前面进行查找 k -2
70 //5. 即下次循环 mid f[k - 1 - 2] - 1
71 k - 2;
72 } else { //找到
73 //需要确定返回的是哪个下标
74 if(mid high) {
75 return mid;
76 } else {
77 return high;
78 }
79 }
80 }
81 return -1;
82 } 代码转载于:https://www.cnblogs.com/justBobo/p/11144914.html
