查找

线性查找二分查找插值查找斐波那契查找

线性查找

按顺序查找，找到了则返回下标

【代码】

public class SeqSearch { public static void main(String[] args) { int[] arr ={1,5,2,6,3,8,9}; int value = 0; for (int i = 0; i < arr.length; i++){ if (value == arr[i]){ System.out.println("找到了，下标为：" + i); return; } } System.out.println("没有找到"); } }

二分查找

也叫折半查找 是对有序数组进行查找。

【代码】

public class BinarySearch { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8,8,8, 9}; int i = binarySearch(arr, 0, arr.length - 1, 8); System.out.println(i); } 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); }if(findVal < midVal){//向左递归 return binarySearch(arr,left,mid-1,findVal); }else {//找到 return mid; } } }

【优化】返回多个下标

//返回多个下标 public static List<Integer> binarySearchs(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 binarySearchs(arr,mid+1,right,findVal); }if(findVal < midVal){//向左递归 return binarySearchs(arr,left,mid-1,findVal); }else {//找到 List<Integer> indexList = new ArrayList<Integer>(); //向mid索引值左边扫描 int temp = mid - 1; while (true){ if (temp < 0 || arr[temp] != findVal){//退出 break; } indexList.add(temp); temp -= 1;//左移 } indexList.add(mid); //向mid索引值右边扫描 temp = mid + 1; while (true){ if (temp > arr.length -1 || arr[temp] != findVal){ break; } indexList.add(temp); temp += 1; } return indexList; } }

插值查找

插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。 int mid = left+(right–left)*(findVal–arr[left])/(arr[right]–arr[left])

注意事项 1、对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找,速度较快. 2、关键字分布不均匀的情况下，该方法不一定比折半查找要好

【代码】

public class InsertValueSearch { public static void main(String[] args) { int[] arr = {1,2,3,4,5,6,7,8,9}; int i = insertValueSearch(arr, 0, arr.length - 1, 2); System.out.println(i); } public static int insertValueSearch(int[] arr,int left,int right,int findVal){ //findVal < arr[0] || findVal > arr[arr.length-1] 是必要的 //防止 mid 越界 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; } } }

斐波那契查找

也叫 黄金分割法查找

待续。。。。。