4大查找算法
1.背景
查找算法经常被面试问到...
2.代码
2.1.线性查找算法
package com.ldp.structure.demo03Search; import org.junit.Test; import java.util.ArrayList; import java.util.List; /** * @create 04/17 12:03 * @description <p> * 线性查找 * </p> */ public class Test01LinearSearch { /** * 测试线性查找 */ @Test public void test01() { int[] array = {14, 57, 2, 1, 96, 74, 9, 2, 708}; List<Integer> integers = linearSearch(array, 2); System.out.println(integers); } /** * 线性查找 * * @param array * @param searchValue * @return */ public List<Integer> linearSearch(int[] array, int searchValue) { ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < array.length; i++) { if (searchValue == array[i]) { list.add(i); } } return list; } }
2.2.二分查找算法
package com.ldp.structure.demo03Search; import org.junit.Test; import java.util.ArrayList; import java.util.List; /** * @create 04/17 12:09 * @description <P> * 二分查找 * </P> */ public class Test02TwoBranchSearch { @Test public void test01() { int[] array = {1, 2, 3, 4, 5}; int searchSingle = twoBranchSearchSingle(array, 0, array.length - 1, -4); System.out.println(searchSingle); } @Test public void test02() { int[] array = {1, 2, 2, 3, 4, 5, 6, 7, 8}; List<Integer> searchMore = twoBranchSearchMore(array, 0, array.length - 1, 2); System.out.println(-2= + searchMore); } /** * 前提改数组是一个有序数组 * 二分查找-查询单个 * * @param array * @param left * @param right * @param searchValue * @return */ public int twoBranchSearchSingle(int[] array, int left, int right, int searchValue) { if (left >= right) { return -1; } int middle = (left + right) / 2; if (searchValue < array[middle]) { // 左递归 return twoBranchSearchSingle(array, left, middle, searchValue); } else if (searchValue > array[middle]) {// 右递归 return twoBranchSearchSingle(array, middle + 1, right, searchValue); } else { return middle; } } /** * 前提改数组是一个有序数组 * 二分查找-查询多个 * * @param array * @param left * @param right * @param searchValue * @return */ public List<Integer> twoBranchSearchMore(int[] array, int left, int right, int searchValue) { if (left >= right) { // 没有找到的情况 return new ArrayList<>(); } int middle = (left + right) / 2; if (searchValue < array[middle]) { // 左递归 return twoBranchSearchMore(array, left, middle, searchValue); } else if (searchValue > array[middle]) {// 右递归 return twoBranchSearchMore(array, middle + 1, right, searchValue); } else { // 因为数组是有序的,因此如果查找到了的话,可能左边,右边都有相同的值,如: [1,2,2,3,4,5,6,7,8] List<Integer> result = new ArrayList<>(); result.add(middle); // 向左查找满足条件的值 for (int i = (middle - 1); i >= left; i--) { if (array[i] == searchValue) { result.add(i); } else { break; } } // 向右查找满足条件的值 for (int i = (middle + 1); i <= right; i++) { if (array[i] == searchValue) { result.add(i); } else { break; } } return result; } } }
2.3.插值查找算法
package com.ldp.structure.demo03Search; import org.junit.Test; /** * @create 04/17 12:09 * @description <P> * 插值查找-算法(数组必须有序) * </P> */ public class Test03InsertValueSearch { // 统计分解次数 int count = 0; @Test public void test01() { int[] array = {1, 2, 2, 3, 4, 5, 6, 7, 8}; Integer numIndex = insertValueSearchSingle(array, 0, array.length - 1, 8); System.out.println(分解次数: + count + ,下标为: + numIndex); } /** * 前提改数组是一个有序数组 * 二分查找-查询单个 * * @param array * @param left * @param right * @param searchValue * @return */ public int insertValueSearchSingle(int[] array, int left, int right, int searchValue) { // 统计分解次数 count++; // array[left] > searchValue 或者 array[right] < searchValue,查找的值不在序列范围内 if (left >= right || array[left] > searchValue || array[right] < searchValue) { return -1; } // int middle = (left + right) / 2; // 二分查找算法公式 int middle = left + (right - left) * (searchValue - array[left]) / (array[right] - array[left]); if (searchValue < array[middle]) { // 左递归 return insertValueSearchSingle(array, left, middle, searchValue); } else if (searchValue > array[middle]) {// 右递归 return insertValueSearchSingle(array, middle + 1, right, searchValue); } else { return middle; } } }
2.4.斐波那契(黄金分割)查找算法
package com.ldp.structure.demo03Search; import org.junit.Test; import java.util.Arrays; /** * @create 04/17 12:09 * @description <P> * 斐波那契(黄金分割)查找-算法(数组必须有序) * </P> */ public class Test04GoldenSearch { // 统计分解次数 @Test public void test01() { int[] array = {1, 2, 2, 3, 4, 5, 6, 7, 8}; Integer numIndex = goldenSearchSingle(array, 4); System.out.println(下标为: + numIndex); } /** * 斐波那契(黄金分割)查找-算法(数组必须有序) * * @param array * @param searchValue * @return */ public int goldenSearchSingle(int[] array, int searchValue) { // 左侧 int left = 0; int right = array.length - 1; // 不在查找范围内 if (searchValue < array[left] || searchValue > array[right]) { return -1; } // 斐波那契数组 int[] fbArray = fb(); // k为斐波那契数组的下标,这里默认0 int k = 0; // 寻找一个合适的k while (right > fbArray[k] - 1) { k++; } // 如果 fbArray[k]> right,补充新的数组 int[] tempArray = Arrays.copyOf(array, fbArray[k]); // 使用原来数组的最后一个值填充,新数组中为空的值, // 比如原数组为array=[1,2,3,4,5],tempArray=[1,2,3,4,5,无值,无值],填充后tempArray=[1,2,3,4,5,5,5],即使用最后一个值填充 for (int i = right; i < fbArray[k]; i++) { tempArray[i] = array[right]; } while (left <= right) { int middle = left + fbArray[k] - 1; // 斐波那契公式 if (searchValue < tempArray[middle]) { // 在左侧找 right = middle - 1; k--; } else if (searchValue > tempArray[middle]) { // 在右侧找 left = middle + 1; k = k - 2; // 公式 f(k)=f(k-1)+f(k-2)==> 右拆分相当于对 f(k-2),继续拆分f(k-2)=f(k-3)+f(k-4),因此k=k-2 } else { // 确定返回下标 if (middle > right) { return right; } else { return middle; } } } return -1; } /** * 获取一个斐波那契数组 * * @return */ public int[] fb() { int[] fbArray = new int[20]; fbArray[0] = 1; fbArray[1] = 1; for (int i = 2; i < 20; i++) { fbArray[i] = fbArray[i - 1] + fbArray[i - 2]; } return fbArray; } }