查找算法
线性查找算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| public class SeqSearch { public static void main(String[] args) { int[] arr= {1,9,11,-1,34,89}; int index=seqSearch(arr, -11); if (index==-1) { System.out.println("没有找到该值"); }else { System.out.println("找到了,下标为 "+index); } }
public static int seqSearch(int[] arr,int value) { for (int i = 0; i < arr.length; i++) { if (arr[i]==value) { return i; } } return -1; } }
|
二分查找算法
请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示”没有这个数”。
二分查找的思路分析
- 首先确定该数组最中间的下标mid=(left+right)/2
- 然后让需要查找的数findVal和arr[mid]比较
- findVal>arr[mid],说明要查找的数在mid的右边,因此需要递归向右查找
- findVal<arr[mid],说明要查找的数在mid的右边,因此需要递归向右左查找
- findVal==arr[mid],说明找到要查找的值,就返回
//什么时候结束递归
- 找到就结束递归
- 递归完整个数组,仍然没有找到findVal,也需要结束递归 当left>right就需要退出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
public class BinarySearch { public static void main(String[] args) { int[] arr= {1,8,10,1000,1234}; int index=binarySearch(arr, 0, arr.length-1, 1234); if (index==-1) { System.out.println("没有找到该值"); }else { System.out.println("找到了,下标为 "+index); } }
public static int binarySearch(int[] arr,int left,int right,int findVal) {
if (left>right) { return -1; } int mid=(left+right)/2; int midVal=arr[mid]; if (findVal>midVal) { return binarySearch(arr, mid+1, right, findVal); }else if (findVal<midVal) { return binarySearch(arr, left, mid-1, findVal); }else { return mid; } } }
|
课后思考题: {1,8, 10, 89, 1000, 1000,1234} 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| import java.util.ArrayList; import java.util.List;
public class BinarySearch { public static void main(String[] args) { int[] arr = { 1, 8, 10, 1000, 1000, 1234 }; List<Integer> index = binarySearch2(arr, 0, arr.length - 1, 1000); if (index.size() == 0) { System.out.println("没有找到该值"); } else { System.out.println("找到了,下标为 " + index); } }
public static int binarySearch(int[] arr, int left, int right, int findVal) { if (left > right) { return -1; } int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { return binarySearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySearch(arr, left, mid - 1, findVal); } else { return mid; } }
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) { if (left > right) { return new ArrayList<Integer>(); } int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { return binarySearch2(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySearch2(arr, left, mid - 1, findVal); } else { List<Integer> resIndexList = new ArrayList<Integer>(); int temp = mid - 1; while (true) { if (temp < 0 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp -= 1; } resIndexList.add(mid); temp = mid + 1; while (true) { if (temp > arr.length - 1 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp += 1; } return resIndexList; } }
}
|
插值查找算法
插值查找原理介绍:
插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。
将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.
key 就是前面我们讲的 findVal
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓改成↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| import java.util.ArrayList; import java.util.List;
public class InsertValueSearch { public static void main(String[] args) { int[] arr=new int[100]; for (int i = 0; i < arr.length; i++) { arr[i]=i+1; } List<Integer> index = insertValueSearch(arr, 0, arr.length-1, 4); if (index.size() == 0) { System.out.println("没有找到该值"); } else { System.out.println("找到了,下标为 " + index); } }
public static List<Integer> insertValueSearch(int[] arr,int left,int right,int findVal) {
if (left>right||findVal<arr[0]||findVal>arr[arr.length-1]) { return new ArrayList<Integer>(); }
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]) ; int midVal=arr[mid]; if (findVal>midVal) { return insertValueSearch(arr, mid+1, right, findVal); }else if (findVal<midVal) { return insertValueSearch(arr, left, mid-1, findVal); }else { List<Integer> resIndexList = new ArrayList<Integer>(); int temp = mid - 1; while (true) { if (temp < 0 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp -= 1; } resIndexList.add(mid); temp = mid + 1; while (true) { if (temp > arr.length - 1 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp += 1; } return resIndexList; } } }
|
插值查找注意事项:
1)对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.
2)关键字分布不均匀的情况下,该方法不一定比折半查找要好
斐波那契(黄金分割法)查找算法
斐波那契(黄金分割法)查找基本介绍:
- 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神奇的数字,会带来意向不大的效果。
- 斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例,无限接近 黄金分割值0.618
斐波那契(黄金分割法)原理:
斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1 (F代表斐波那契数列),如下图所示
对F(k-1)-1的理解:
- 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质,可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 。该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段,即如上图所示。从而中间位置为mid=low+F(k-1)-1
- 类似的,每一子段也可以用相同的方式分割
- 但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可。
斐波那契查找应用案例:
请对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示”没有这个数”。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
| import java.util.Arrays;
public class FibonacciSearch { public static int maxSize = 20;
public static void main(String[] args) { int[] arr = { 1, 8, 10, 89, 1000, 1234 }; System.out.println("index="+fibSearch(arr, 1)); }
public static int[] fib() { int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i < maxSize; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; }
public static int fibSearch(int[] a, int key) { int low = 0; int high = a.length - 1; int k = 0; int mid = 0; int[] f = fib(); while (high > f[k] - 1) { k++; } int[] temp = Arrays.copyOf(a, f[k]); for (int i = high + 1; i < temp.length; i++) { temp[i] = a[high]; } while (low <= high) { mid = low + f[k - 1] - 1; if (key<temp[mid]) { high=mid-1; k--; }else if(key>temp[mid]){ low=mid+1; k-=2; }else { if (mid<=high) { return mid; }else { return high; } } } return -1; } }
|