一. 查找算法介绍
顺序(线性)查找二分查找/折半查找插值查找斐波那契查找顺序查找
代码展示:
package com.qiu.search; public class SeqSearch { public static void main(String[] args) { int[] arr = {1,211,54,84,56}; int index = seqSearch(arr,211); if (index == -1){ System.out.println("没有找到这个值!"); }else { System.out.println("你要找的值下标为:"+index); } } /** * 实现的线性查找是找到一个满足条件的值就返回 * @param arr * @param value * @return */ 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},输入一个数 看看该数组是否存在此数,并且求出下标,如果没有就提示没有这个数
二分查找的思路分析: 1.首先确定该数组的中间的下标 mid = (left+right)/2 2. 然后让需要查找的数findVal和arr[mid]比较 3. 情况一:findVal>arr[mid]说明你要查找的数在mid的右边.因此需要递归的向右查找 4. 情况二:findVal<>arr[mid]说明你要查找的数在mid的左边.因此需要递归的向右查找 5. findVal == arr[mid]说明找到,就返回
//什么时候结束递归
找到就结束递归递归完整个数组,仍然没有找到findVal,也需要结束递归当left>right就需要退出 代码实现: package com.qiu.search; /** * @author qiuzhikang */ public class BinarySearch { public static void main(String[] args) { int[] arr = {1,8,10,89,1000,1234}; int resindex = binarySearch(arr,0,arr.length-1,8); System.out.println(resindex); } //二分查找算法 /** * * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findVal 要查找的值 * @return 如果找到就返回下标,没有就找到-1 */ 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; } } }如果说有一个有序数组中,有多个重复的数据,全部找到并发返回下标应该怎么弄
分析思路:
在找到mid值时不要马上返回向mid索引值的左边扫描,将满足值的元素的下标加入到集合中向mid索引值的右边进行扫描,将满足值的元素的下标加入到集合中最后将arrayList返回 package com.qiu.search; import java.util.ArrayList; import java.util.List; public class BinarySearch1 { public static void main(String[] args) { int[] arr = {1,3,5,7,8,8,9,16,17,199,215,222}; List<Integer> list = binarySearch2(arr, 0, arr.length - 1, 8); System.out.println(list); } //二分查找算法 /** * * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findVal 要查找的值 * @return 如果找到就返回下标,没有就找到-1 */ public static ArrayList<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 { ArrayList<Integer> resIndexList = new ArrayList<>(); int temp = mid - 1; while (true) { if (temp < 0 || arr[temp] != findVal) { break; } //否则就将这个temp放入到resIndexList中 resIndexList.add(temp); //temp左移 temp -= 1; } resIndexList.add(mid); //向mid索引值的右边扫描,将所有满足1000的元素的下标加入到集合ArrayList中 temp = mid + 1; while (true) { if (temp > arr.length - 1 || arr[temp] != findVal) { break; } //否则就将这个temp放入到resIndexList中 resIndexList.add(temp); //temp右移 temp += 1; } return resIndexList; } } }找到重复的就直接判断查找
二分查找算法(非递归)介绍
前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7)二分查找算法(非递归)代码实现
数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找， 要求使用非递归的方式完成.
代码实现:
package com.qiu.binarysearchnorecursion; public class BinarySearchNoRecur { public static void main(String[] args) { int[] arr = {1,3, 8, 10, 11, 67, 100}; int index = binarySearch(arr,-8); System.out.println("index = " + index); } /** * //二分查找的非递归实现 * @param arr 待查找的数组 * @param target 需要查找的数 * @return 返回对应的下标,没有就返回-1 */ public static int binarySearch(int[] arr ,int target){ int left = 0; int right = arr.length-1; while(left <= right){ //满足条件就可以继续查找 int mid = (left + right) / 2; if (arr[mid] == target){ return mid; }else if (arr[mid] > target){ //需要向左边查找 right = mid -1; }else{ //需要向右边查找 left = mid + 1; } } return -1; } }插值查找
插值查找算法原理介绍
插值查找算法类似于二分查找,不同的是插值查找每次从自适应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])4.举例说明插值查找算法1-100的演示
package com.qiu.search; public class InsertValSearch { public static void main(String[] args) { int[] arr = new int[100]; for (int i = 0; i < 100; i++) { arr[i] = i+1; } int valueSearch = insertValueSearch(arr, 0, arr.length - 1, 100); System.out.println(valueSearch); } //编写插值查找的算法:插值算法也要求算法有序 public static int insertValueSearch(int[] arr,int left,int right,int findVal){ //注意findVal < arr[0] || findVal > arr[arr.length-1]是必须需要的.否则可能越界 if (left > right || findVal < arr[0] || findVal > arr[arr.length-1]){ return -1; } //求出mid 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 { return mid; } } }插值查找相较于二分查找:减少了查找最大值和最小值的查找次数.
插值查找注意事项：
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.关键字分布不均匀的情况下，该方法不一定比折半查找要好斐波那契(黄金分割法)查找算法
斐波那契查找的基本介绍:
黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是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} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。
package com.qiu.search; import java.util.Arrays; public class FibonacciSearch { public static int maxSize = 20; public static void main(String[] args) { int[] arr = {1,2,3,5,7,9,10,50,60,500,900}; System.out.println(fibSearch(arr,3)); } //因为后面我们mid = left+F(k-1)-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; } //编写斐波那契查找算法 //使用非递归的方式来实现 /** * * @param a 数组 * @param key 我们需要查找的关键码 * @return 返回对应的下标 */ 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(); //获取到斐波那契分割数值的下标 //顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可 while(high > f[k] - 1){ k++; } //因为f[k] 值可能大于a的长度,因此我们需要使用到ArrayS类,构造一个新的数组,并指向a[] //不足的部分使用0填充 int[] temp = Arrays.copyOf(a,f[k]); //实际上需要使用a数组的最后的数填充到temp,因为拷贝到新的数组后长度变长了,后面的数都是用0来补充 //但是我们需要数组有序,所以我们将数组最后的0值全部填充为数组的最后一个数 for (int i = high+1; i <temp.length ; i++) { temp[i] = a[high]; } //使用while来循环处理,找到我们的数key while(low <= high){ //只要满足了条件才可以找 mid = low + f[k-1]- 1; if (key < temp[mid]){ //应该向数组的前边查找 high = mid - 1; //为什么是k-- //1. 全部元素 = 前面的元素+后边的元素 //2. f[k] = f[k-1]+f[k-2] //因为前面有f[k-1]个元素,所以我们可以继续拆分f[k-1] = f[k-2]+f[k-3] //即在f[k-1]的前面继续查找 k-- //下次循环时,mid = f[k-1-1]-1 k--; }else if (key > temp[mid]){ //我们应该向数组的后边查找(右边) low = mid + 1; //为什么是k-=2 /* 说明 1. 全部元素 = 前面的元素+后边的元素 2. f[k] = f[k-1]+f[k-2] 3. 因为后面我们有f[k-2],所以可以继续拆分f[k-1] = f[k-3]+f[k-4] 4.即在f[k-2]的前面进行查找 k-=2 5.即下次循环mid = f[k-1-2]-1 */ k-=2; }else{ //找到了,需要确定的是返回哪个下标 if (mid <= high){ return mid; }else{ return high; } } } return -1; } }