package com.lin.search_0303; public class SeqSearch { public static void main(String[] args) { int arr[] = {1,2,7,3,4,5,6,7,7,455,454,-1,7}; int index = seqSearch(arr, -1); if(index == -1) { System.out.println("没有找到该数字!"); } else { System.out.println("找到了,下标为:" + index); } String find = seqSearchAll(arr, 7); if(find.equals("kong")) { System.out.println("没有找到!"); } else { System.out.println(find); } } // 找到一个就返回 public static int seqSearch(int[] arr, int value) { for (int i = 0; i < arr.length; i++) { if(value == arr[i]) return i; } return -1; } // 查找多个 public static String seqSearchAll(int[] arr, int value) { String resString = ""; for (int i = 0; i < arr.length; i++) { if(value == arr[i]) { resString += i + " "; } } if(!resString.isEmpty()) { return resString; } else { return "kong"; } } }
package com.lin.search_0303; import java.util.ArrayList; import java.util.List; public class BinarySearch { public static void main(String[] args) { int arr[] = { 1, 8, 10, 89, 1000, 1234 ,1234, 1234}; int index = binarySearch(arr, 0, arr.length-1, 0); System.out.println(index); ArrayList<Integer> resList = binarySearchAll(arr, 0, arr.length-1, 12342); if(resList.size()!=0) { for (Integer integer : resList) { System.out.println(integer); } } else { System.out.println("没有找到"); } } /** * * @Description:二分查找 * @author LinZM * @date 2021-3-3 21:38:42 * @version V1.8 * @param arr 数组 * @param left 左边索引 * @param right 右边索引 * @param findVal 要查找的值 * @return 如果找到就返回下标,如果没有找到就返回-1 */ public static int binarySearch(int[] arr, int left, int right, int findVal) { // 当left>right时,说明递归整个数组都没有找到该值 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 ArrayList<Integer> binarySearchAll(int[] arr, int left, int right, int findVal) { // 当left>right时,说明递归整个数组都没有找到该值 if(left>right) { return new ArrayList<Integer>(); } int mid = (left+right)/2; int midVal = arr[mid]; if(findVal > midVal) { // 向右递归 return binarySearchAll(arr, mid+1, right, findVal); } else if(findVal < midVal) { return binarySearchAll(arr, left, mid-1, findVal); } else{ ArrayList<Integer> resIndex = new ArrayList<Integer>(); int temp = mid-1; while(true) { if(temp < 0 || arr[temp] != findVal) { break; } resIndex.add(temp); temp -= 1; } resIndex.add(mid); temp = mid+1; while(true) { if(temp > arr.length-1 || arr[temp] != findVal) { break; } resIndex.add(temp); temp += 1; } return resIndex; } } }
package com.lin.search_0303; import java.util.Arrays; 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; } System.out.println(Arrays.toString(arr)); int insertValueSearch = insertValueSearch(arr, 0, arr.length-1, 1); System.out.println(insertValueSearch); } // 插值查找 public static int insertValueSearch(int[] arr, int left, int right, int findVal) { if(left > right || findVal < arr[0] || findVal > arr[arr.length-1]) { return -1; } 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; } } }
package com.lin.search_0303; 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(fibSearch(arr, 10)); } // mid = low + 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; } // 查找算法 public static int fibSearch(int[] arr, int key) { int low = 0; int high = arr.length-1; int k = 0; // 斐波那契分割数值的下标 int mid = 0; int f[] = fib(); // 获取k while(high > f[k] - 1) { k++; } // 因为f[k]值可能大于arr的长度,因此要构造一个新的数组,并指向arr[] // 不足的部分会使用0填充 int[] temp = Arrays.copyOf(arr, f[k]); // 实际上需要使用arr数组最后的数填充temp for (int i = high+1; i < temp.length; i++) { temp[i] = arr[high]; } while(low <= high) { mid = low + f[k-1] - 1; if(key < temp[mid]) { high = mid - 1; //f[k] = f[k-1] + f[k-2] //前面有k-1个元素所以 // f[k-1] = f[k-2]+f[k-3] k--; } else if(key > temp[mid]) { low = mid + 1; //f[k] = f[k-1] + f[k-2] //后面有k-2个元素所以 // f[k-1] = f[k-3]+f[k-4] k -= 2; } else { if(mid <= high) { return mid; } else { return high; } } } return -1; } }
仅供参考,有错误还请指出!
有什么想法,评论区留言,互相指教指教。
觉得不错的可以点一下右边的推荐哟