常见查找算法原理与应用详解

查找算法原理与应用

基本查找（顺序查找）

顺序查找是最简单的查找算法，从数据结构的一端开始，逐个检查每个元素，直到找到目标元素或遍历完整个结构。适用于无序列表或小规模数据。

应用场景：小型数据集或无序数据查找。

public class LinearSearch {public static int search(int[] arr, int target) {for (int i = 0; i < arr.length; i++) {if (arr[i] == target) {return i;}}return -1;}
}

二分查找（折半查找）

二分查找要求数据必须有序。通过将目标值与中间元素比较，可以确定目标值在左半部分还是右半部分，逐步缩小范围。

应用场景：有序数组的高效查找。

public class BinarySearch {public static int search(int[] arr, int target) {int left = 0, right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}
}

插值查找

插值查找是二分查找的改进，通过计算目标值的位置来缩小范围。适用于数据分布均匀的有序数组。

应用场景：均匀分布的有序数据。

public class InterpolationSearch {public static int search(int[] arr, int target) {int left = 0, right = arr.length - 1;while (left <= right && target >= arr[left] && target <= arr[right]) {int pos = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]);if (arr[pos] == target) {return pos;} else if (arr[pos] < target) {left = pos + 1;} else {right = pos - 1;}}return -1;}
}

斐波那契查找

斐波那契查找利用斐波那契数列分割数组，适用于有序数据且数据量较大时。

应用场景：有序数组且数据量大时的高效查找。

public class FibonacciSearch {public static int search(int[] arr, int target) {int fibMMm2 = 0, fibMMm1 = 1, fibM = fibMMm2 + fibMMm1;while (fibM < arr.length) {fibMMm2 = fibMMm1;fibMMm1 = fibM;fibM = fibMMm2 + fibMMm1;}int offset = -1;while (fibM > 1) {int i = Math.min(offset + fibMMm2, arr.length - 1);if (arr[i] < target) {fibM = fibMMm1;fibMMm1 = fibMMm2;fibMMm2 = fibM - fibMMm1;offset = i;} else if (arr[i] > target) {fibM = fibMMm2;fibMMm1 = fibMMm1 - fibMMm2;fibMMm2 = fibM - fibMMm1;} else {return i;}}if (fibMMm1 == 1 && arr[offset + 1] == target) {return offset + 1;}return -1;}
}

分块查找

分块查找将数据划分为若干块，块内无序但块间有序。通过索引快速定位块，再在块内进行顺序查找。

应用场景：数据分块存储且块间有序的查找。

public class BlockSearch {public static int search(int[] arr, int target, int blockSize) {int blockIndex = 0;while (blockIndex * blockSize < arr.length && arr[blockIndex * blockSize] <= target) {blockIndex++;}blockIndex--;int start = blockIndex * blockSize;int end = Math.min(start + blockSize, arr.length);for (int i = start; i < end; i++) {if (arr[i] == target) {return i;}}return -1;}
}

以下是几种适用于分块扩展查找的 Java 算法实现示例，涵盖不同场景需求：

基本分块查找算法

分块查找结合顺序查找和二分查找的思想，适合数据分块有序的场景。

public class BlockSearch {private int[] data;private int blockSize;private int[] maxValues; // 每块最大值public BlockSearch(int[] data, int blockSize) {this.data = data;this.blockSize = blockSize;this.maxValues = new int[(data.length + blockSize - 1) / blockSize];// 初始化每块最大值for (int i = 0; i < data.length; i += blockSize) {int max = Integer.MIN_VALUE;int blockEnd = Math.min(i + blockSize, data.length);for (int j = i; j < blockEnd; j++) {if (data[j] > max) max = data[j];}maxValues[i / blockSize] = max;}}public int search(int target) {// 先确定目标所在块int blockIndex = 0;while (blockIndex < maxValues.length && target > maxValues[blockIndex]) {blockIndex++;}// 块内顺序查找int start = blockIndex * blockSize;int end = Math.min(start + blockSize, data.length);for (int i = start; i < end; i++) {if (data[i] == target) return i;}return -1; // 未找到}
}

动态分块扩展查找

适用于需要动态调整分块大小的场景。

public class DynamicBlockSearch {private List<Integer> data;private int minBlockSize;private List<List<Integer>> blocks;public DynamicBlockSearch(List<Integer> data, int minBlockSize) {this.data = new ArrayList<>(data);this.minBlockSize = minBlockSize;rebuildBlocks();}private void rebuildBlocks() {blocks = new ArrayList<>();int currentBlockSize = Math.max(minBlockSize, (int) Math.sqrt(data.size()));for (int i = 0; i < data.size(); i += currentBlockSize) {int end = Math.min(i + currentBlockSize, data.size());blocks.add(new ArrayList<>(data.subList(i, end)));}}public int search(int target) {for (List<Integer> block : blocks) {if (block.get(block.size() - 1) >= target) {for (int i = 0; i < block.size(); i++) {if (block.get(i) == target) {return data.indexOf(target);}}break;}}return -1;}public void insert(int value) {data.add(value);rebuildBlocks();}
}

跳跃表实现分块扩展

利用跳跃表的层级结构实现高效分块查找。

import java.util.Random;class SkipListNode {int value;SkipListNode[] forward;SkipListNode(int value, int level) {this.value = value;this.forward = new SkipListNode[level + 1];}
}public class SkipListBlockSearch {private static final float PROBABILITY = 0.5f;private SkipListNode header;private int maxLevel;private int size;private Random random;public SkipListBlockSearch() {this.header = new SkipListNode(Integer.MIN_VALUE, 0);this.maxLevel = 0;this.size = 0;this.random = new Random();}private int randomLevel() {int level = 0;while (random.nextFloat() < PROBABILITY && level < maxLevel + 1) {level++;}return level;}public void insert(int value) {int newLevel = randomLevel();if (newLevel > maxLevel) {increaseLevel(newLevel);}SkipListNode newNode = new SkipListNode(value, newLevel);SkipListNode current = header;for (int i = maxLevel; i >= 0; i--) {while (current.forward[i] != null && current.forward[i].value < value) {current = current.forward[i];}if (i <= newLevel) {newNode.forward[i] = current.forward[i];current.forward[i] = newNode;}}size++;}private void increaseLevel(int newLevel) {SkipListNode[] newForward = new SkipListNode[newLevel + 1];System.arraycopy(header.forward, 0, newForward, 0, maxLevel + 1);header.forward = newForward;maxLevel = newLevel;}public boolean search(int target) {SkipListNode current = header;for (int i = maxLevel; i >= 0; i--) {while (current.forward[i] != null && current.forward[i].value < target) {current = current.forward[i];}}current = current.forward[0];return current != null && current.value == target;}
}

多级分块索引

适用于超大规模数据的分块扩展查找。

public class MultiLevelBlockSearch {private int[][] data;private int[] blockIndices;private int blockSize;public MultiLevelBlockSearch(int[] data, int blockSize) {this.blockSize = blockSize;int numBlocks = (data.length + blockSize - 1) / blockSize;this.blockIndices = new int[numBlocks];// 第一级索引：块最大值for (int i = 0; i < data.length; i += blockSize) {int max = Integer.MIN_VALUE;int end = Math.min(i + blockSize, data.length);for (int j = i; j < end; j++) {if (data[j] > max) max = data[j];}blockIndices[i / blockSize] = max;}// 第二级数据分块this.data = new int[numBlocks][];for (int i = 0; i < numBlocks; i++) {int start = i * blockSize;int end = Math.min(start + blockSize, data.length);this.data[i] = Arrays.copyOfRange(data, start, end);}}public int search(int target) {// 在第一级索引中查找块int blockIdx = 0;while (blockIdx < blockIndices.length && target > blockIndices[blockIdx]) {blockIdx++;}if (blockIdx >= blockIndices.length) return -1;// 在第二级数据块中查找int[] block = data[blockIdx];for (int i = 0; i < block.length; i++) {if (block[i] == target) {return blockIdx * blockSize + i;}}return -1;}
}

这些实现涵盖了从基础到高级的分块扩展查找算法，可根据具体数据特征和性能要求选择合适的方法。动态分块和跳跃表实现更适合需要频繁插入的场景，而多级索引适合静态大数据集。

哈希查找

哈希查找通过哈希函数将键映射到存储位置，实现快速查找。冲突处理常用链地址法或开放地址法。

应用场景：快速查找，如字典、缓存等。

import java.util.HashMap;public class HashSearch {public static void main(String[] args) {HashMap<Integer, String> map = new HashMap<>();map.put(1, "Apple");map.put(2, "Banana");map.put(3, "Cherry");String result = map.get(2);System.out.println(result); // Output: Banana}
}