查找算法

1.二分查找

介绍

二分查找（Binary Search）是一种高效的查找算法，也叫折半查找。核心思想：对于一个有序的数据集合，每次查找都将查找范围缩小为原来的一半，直到找到目标值或确定目标值不存在。二分查找要求数据必须是有序的，经常应用于数组等支持随机访问的数据结构里。跟线性查找相比，二分查找的效率要高得多，特别是对于大规模数据集。

算法步骤

1. 确定查找范围的左边界 left 和右边界 right
2. 计算中间位置 mid = (left + right) / 2（注意整数溢出问题，更安全的做法是 mid = left + (right - left) / 2）
3. 将中间位置的元素与目标值比较
   • 如果中间元素等于目标值，查找成功，返回中间元素的位置
   • 如果中间元素大于目标值，目标值可能在左半部分，将右边界调整为 mid - 1
   • 如果中间元素小于目标值，目标值可能在右半部分，将左边界调整为 mid + 1
4. 重复步骤2-3，直到找到目标值或者左边界大于右边界（此时表示目标值不存在）

核心特性

• 要求有序：二分查找只适用于有序数据集合
• 时间复杂度：O(log n)，在大规模数据集上非常高效
• 空间复杂度：迭代实现为O(1)，递归实现为O(log n)（因为递归调用栈的深度）
• 随机访问：要求数据结构支持O(1)时间复杂度的随机访问（比如数组）

优缺点

优点

• 查找效率非常高，时间复杂度为 O(log n)
• 在大规模数据集上表现优异
• 实现相对简单
• 不需要额外的空间（迭代实现）

缺点

• 要求数据必须是有序的
• 只适用于支持随机访问的数据结构（如数组）
• 对于频繁插入和删除的数据结构，维护有序性的成本很高
• 不适合小数据量的查找（这种情况下线性查找可能更快）

public static int findFirstEqual(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            // 找到目标值，但需要继续向左查找是否有相同值
            result = mid;
            right = mid - 1;
        }
    }

    return result;
}

2.跳跃查找

介绍

跳跃查找（Jump Search）是一种在有序数组中查找元素的算法，核心思想是通过跳过固定步长的元素来缩小搜索范围，然后在缩小的区间内进行线性查找。跳跃查找是二分查找和线性查找的混合体，特别适合大型有序数据集。

跳跃查找的效率取决于步长的选择。在最佳情况下，跳跃查找的时间复杂度可以达到 O(√n)，优于线性查找的 O(n)，但不如二分查找的 O(log n)。但是在一些具体场景下，跳跃查找比二分查找表现更好，比如当内存中访问顺序元素比随机访问更高效的时候。

算法步骤

1. 确定跳跃步长（通常取 √n，n 是数组长度）
2. 从数组开头开始，每次跳过步长个元素，直到找到大于或等于目标值的元素或达到数组末尾
3. 如果找到的元素大于目标值，则回退一步，在该区间内进行线性查找
4. 如果找到目标值，返回其索引；否则返回未找到标识

核心特性

• 分块查找：将数组分成大小为 √n 的块，跳跃式地查找
• 步长选择：最优步长为 √n，在时间和空间复杂度间取得平衡
• 时间复杂度：平均情况为 O(√n)
• 空间复杂度：O(1)，不需要额外空间
• 适用条件：必须在有序数组上进行操作

优缺点

优点

• 比线性查找更高效，时间复杂度为 O(√n)
• 比二分查找更易于实现
• 在链表等只能顺序访问的数据结构上有优势
• 良好的内存局部性，更利于缓存命中

缺点

• 时间复杂度不如二分查找的 O(log n)
• 性能对步长的选择比较敏感
• 必须是有序数组
• 对于小数组，优势不明显
• 针对频繁动态变化的数据结构，需要重新计算最优步长

function jumpSearch(arr, target) {
    const n = arr.length;

    // 确定最佳步长
    const step = Math.floor(Math.sqrt(n));

    // 跳跃查找阶段
    let prev = 0;
    while (arr[Math.min(step, n) - 1] < target) {
        prev = step;
        step += Math.floor(Math.sqrt(n));
        if (prev >= n) {
            return -1;  // 未找到元素
        }
    }

    // 线性查找阶段
    while (arr[prev] < target) {
        prev++;

        // 如果已到达下一步长或数组末尾，则未找到元素
        if (prev == Math.min(step, n)) {
            return -1;
        }
    }

    // 检查是否找到目标元素
    if (arr[prev] == target) {
        return prev;  // 返回元素索引
    }

    return -1;  // 未找到元素
}

// 测试
const arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];
const target = 55;

const index = jumpSearch(arr, target);

if (index !== -1) {
    console.log(`元素 ${target} 在索引 ${index} 处找到`);
} else {
    console.log(`元素 ${target} 未在数组中找到`);
}

3.哈希查找

介绍

哈希查找（Hash Search），又称散列查找，是一种高效的查找算法，它用哈希函数将数据转换为数组下标，然后直接访问数组中的元素。哈希查找的核心思想是将数据元素通过哈希函数映射到哈希表中的位置，实现快速查找。

在理想情况下，哈希查找的时间复杂度为 O(1)，这就意味着无论数据规模多大，查找操作都能在常数时间内完成，这是哈希查找相比其他查找算法（如二分查找、线性查找）的最大优势。

不过使用哈希查找必须要考虑哈希冲突（不同的数据被映射到相同的位置）问题。

算法步骤

1. 设计一个适合数据特点的哈希函数，将数据映射到哈希表的索引位置
2. 构建哈希表，将所有元素通过哈希函数映射、存储到相应位置
3. 解决可能出现的哈希冲突（通常采用链地址法或开放寻址法）
4. 查找时，通过同样的哈希函数计算目标数据的哈希值
5. 根据哈希值定位到哈希表中的位置
6. 如果存在冲突，则按照解决冲突的方法查找目标元素

核心特性

• 快速访问：理想情况下查找时间复杂度为 O(1)
• 哈希函数：哈希查找的核心，将数据映射到数组索引的函数
• 哈希冲突：不同数据映射到相同位置的情况，需要特殊处理
• 空间换时间：通过额外的内存空间换取查找时间的提升
• 负载因子：表示哈希表的填充程度，影响查找效率和冲突概率
• 动态扩容：负载因子过高时，需要扩大哈希表并重新哈希所有元素

优缺点

优点

• 查找、插入和删除操作的平均时间复杂度为 O(1)
• 适用于快速查找
• 不要求数据有序，更灵活
• 支持动态数据集，高效地添加和删除元素
• 通过合适的哈希函数和解决冲突策略，能实现非常优秀的性能

缺点

• 哈希冲突会降低查找效率，最坏情况下时间复杂度可能退化到 O(n)
• 需要额外的空间存储哈希表
• 不支持范围查询，不适合按顺序遍历场景
• 负载因子过高会导致性能下降，过低会浪费空间

public class HashSearch {
    // 哈希表节点类
    static class Node {
        String key;
        int value;
        Node next;

        public Node(String key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    // 哈希表类
    static class HashTable {
        private Node[] buckets;
        private int capacity;
        private int size;
        private final float LOAD_FACTOR = 0.75f; // 负载因子阈值

        public HashTable(int capacity) {
            this.capacity = capacity;
            this.buckets = new Node[capacity];
            this.size = 0;
        }

        // 哈希函数
        private int hash(String key) {
            int hash = 0;
            for (char c : key.toCharArray()) {
                hash = (hash * 31 + c) % capacity;
            }
            return Math.abs(hash);
        }

        // 插入键值对
        public void put(String key, int value) {
            if ((float)size / capacity >= LOAD_FACTOR) {
                resize(2 * capacity);
            }

            int index = hash(key);
            Node newNode = new Node(key, value);

            // 如果桶为空，直接插入
            if (buckets[index] == null) {
                buckets[index] = newNode;
                size++;
                return;
            }

            // 处理哈希冲突，使用链地址法
            Node current = buckets[index];

            // 检查是否已存在相同的键
            while (current != null) {
                if (current.key.equals(key)) {
                    current.value = value; // 更新值
                    return;
                }
                if (current.next == null) {
                    break;
                }
                current = current.next;
            }

            // 在链表末尾添加新节点
            current.next = newNode;
            size++;
        }

        // 查找键对应的值
        public Integer get(String key) {
            int index = hash(key);
            Node current = buckets[index];

            // 遍历链表查找匹配的键
            while (current != null) {
                if (current.key.equals(key)) {
                    return current.value;
                }
                current = current.next;
            }

            // 未找到
            return null;
        }

        // 删除键值对
        public boolean remove(String key) {
            int index = hash(key);
            Node current = buckets[index];
            Node prev = null;

            // 查找目标节点
            while (current != null) {
                if (current.key.equals(key)) {
                    break;
                }
                prev = current;
                current = current.next;
            }

            // 未找到目标节点
            if (current == null) {
                return false;
            }

            // 删除节点
            if (prev == null) {
                buckets[index] = current.next;
            } else {
                prev.next = current.next;
            }

            size--;
            return true;
        }

        // 扩容并重新哈希
        private void resize(int newCapacity) {
            Node[] oldBuckets = buckets;

            // 创建新的哈希表
            buckets = new Node[newCapacity];
            capacity = newCapacity;
            size = 0;

            // 重新哈希所有元素
            for (Node bucket : oldBuckets) {
                Node current = bucket;
                while (current != null) {
                    put(current.key, current.value);
                    current = current.next;
                }
            }
        }
    }

    public static void main(String[] args) {
        HashTable hashTable = new HashTable(10);

        // 插入数据
        hashTable.put("apple", 5);
        hashTable.put("banana", 10);
        hashTable.put("orange", 15);
        hashTable.put("grape", 20);

        // 查找数据
        System.out.println("apple: " + hashTable.get("apple"));
        System.out.println("banana: " + hashTable.get("banana"));
        System.out.println("orange: " + hashTable.get("orange"));
        System.out.println("grape: " + hashTable.get("grape"));
        System.out.println("watermelon: " + hashTable.get("watermelon"));

        // 删除数据
        hashTable.remove("orange");
        System.out.println("After removing orange: " + hashTable.get("orange"));
    }
}

---