常见的查找算法
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;//存放 mid 值 int[] f = fib();//获取到斐波那契数列 //获取到斐波那契分割数值的下标 while (high > f[k] - 1){ k++; } //因为 f[k] 值 可能大于 a 的 长度,因此我们需要使用 Arrays 类,构造一个新的数组,并指向 temp[] //不足的部分会使用 0 填充 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]){ if (mid <= high){ return mid; } else { return high; } } 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 { 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; } } return -1; } // 插值查找 public static int insertValueSearch(int[] array, int left, int right, int findVal){ if (left > right || findVal < array[0] || findVal > array[array.length - 1]){ return -1; } int mid = left + (right - left) * (findVal - array[left]) / (array[right] - array[left]); int midVal = array[mid]; if(midVal == findVal){ return mid; } if (findVal > midVal){ return insertValueSearch(array, mid + 1, right, findVal); } else { return insertValueSearch(array, left, mid - 1, findVal); } } // 二分查找算法 /* * @param*/ public static int binarySearch(int[] array, int left, int right, int findVal){ if (left > right){ return -1; } int mid = (left + right) / 2; int midVal = array[mid]; if (findVal == midVal) return mid; if (findVal > midVal) { return binarySearch(array, mid + 1, right, findVal); } else { return binarySearch(array, left, mid - 1, findVal); } } public static ArrayList<Integer> binarySearch2(int[] array, int left, int right, int findVal){ if (left > right){ return new ArrayList<Integer>(); } int mid = (left + right) / 2; int midVal = array[mid]; if (findVal == midVal){ ArrayList<Integer> resIndexlist = new ArrayList<>(); int temp = mid - 1; while (true){ if (temp < 0 || array[temp] != findVal){ break; } resIndexlist.add(temp); temp--; } resIndexlist.add(mid); temp = mid + 1; while (true){ if (temp > array.length -1 || array[temp] != findVal){ break; } resIndexlist.add(temp); temp++; } return resIndexlist; } if (findVal > midVal) { return binarySearch2(array, mid + 1, right, findVal); } else { return binarySearch2(array, left, mid - 1, findVal); } } // 顺序查找 public static int seqSearch(int[] array, int value){ for (int i = 0; i < array.length; i++) { if (array[i] == value){ return i; } } return -1; }
数据结构(java代码实现) 文章被收录于专栏
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。