查找

本章题海战术

典型例题	leetcode题目	leetcode链接
二分查找	leetcode 704	https://leetcode.cn/problems/binary-search/description/
搜索插入位置	leetcode 35	https://leetcode.cn/problems/search-insert-position/description/
在排序数组中查找元素的第一个和最后一个位置	leetcode 34	https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
第一个错误的版本	leetcode 278	https://leetcode.cn/problems/first-bad-version/description/
搜索旋转排序数组	leetcode 33	https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
寻找旋转排序数组中的最小值	leetcode 153	https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
搜索旋转排序数组 II	leetcode 81	https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/description/
寻找旋转排序数组中的最小值 II	leetcode 154	https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/
两数之和	leetcode 1	https://leetcode.cn/problems/two-sum/description/
字母异位词分组	leetcode 49	https://leetcode.cn/problems/group-anagrams/description/
有效的字母异位词	leetcode 242	https://leetcode.cn/problems/valid-anagram/description/
x 的平方根	leetcode 69	https://leetcode.cn/problems/sqrtx/description/
爱吃香蕉的珂珂	leetcode 875	https://leetcode.cn/problems/koko-eating-bananas/description/
有效的完全平方数	leetcode 367	https://leetcode.cn/problems/valid-perfect-square/description/
只出现一次的数字	leetcode 136	https://leetcode.cn/problems/single-number/description/
搜索二维矩阵 II	leetcode 240	https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
寻找峰值	leetcode 162	https://leetcode.cn/problems/find-peak-element/description/
无重复字符的最长子串	leetcode 3	https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
最长连续序列	leetcode 128	https://leetcode.cn/problems/longest-consecutive-sequence/description/
缺失的第一个正数	leetcode 41	https://leetcode.cn/problems/first-missing-positive/description/
二叉搜索树中第 K 小的元素	leetcode 230	https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
删除二叉搜索树中的节点	leetcode 450	https://leetcode.cn/problems/delete-node-in-a-bst/description/
存在重复元素 III	leetcode 220	https://leetcode.cn/problems/contains-duplicate-iii/description/
LRU 缓存	leetcode 146	https://leetcode.cn/problems/lru-cache/description/
O(1) 时间插入、删除和获取随机元素	leetcode 380	https://leetcode.cn/problems/insert-delete-getrandom-o1/description/
基于时间的键值存储	leetcode 981	https://leetcode.cn/problems/time-based-key-value-store/description/

查找

面试官您好，关于常用的查找类算法，我从面试考察优先级、核心原理、Java 落地和高频考点几个维度给您梳理下。核心主要分三类：线性查找、二分查找、哈希查找，其中二分查找及其变种是大厂绝对的高频必考点。

📊 核心查找算法总览对比

算法类型	平均时间复杂度	最坏时间复杂度	空间复杂度	是否要求有序	核心适用场景
线性查找	O(n)	O(n)	O(1)	❌ 不需要	数据量小、无序数组
二分查找	O(logn)	O(logn)	O(1)	✅ 必须有序	数据量大、有序数组 / 有序表
哈希查找	O(1)	O(logn)	O(n)	❌ 不需要	高频查询、键值对匹配场景

🔍 重点算法深度拆解

1. 线性查找 ⭐

• 原理：从头到尾遍历比对，暴力匹配目标值
• 面试定位：基础概念，极少单独考察，一般作为算法复杂度对比基准
• 小优化：可采用哨兵模式减少边界判断，提升极微小的性能

2. 二分查找 ⭐⭐⭐⭐⭐（面试必考）

💡 核心前提：有序数组 + 支持随机访问，本质是分治思想，每次排除一半数据，指数级缩小搜索范围

执行流程图

必答关键点（面试直接加分）

• 边界统一范式：推荐用「左闭右闭」区间，循环条件写 left <= right，边界调整为 left=mid+1 / right=mid-1，逻辑最统一，不易写出死循环
• mid 溢出优化：Java 中禁止写 (left+right)/2，改用 left + (right - left) / 2，避免两个大整数相加导致 int 溢出
• 四大常考变种：
  • 1.查找第一个等于 target 的位置：相等时不直接返回，收缩右边界 right=mid-1，循环结束后校验 left 合法性
  • 2.查找最后一个等于 target 的位置：相等时收缩左边界 left=mid+1，循环结束后校验 right 合法性
  • 3.查找第一个大于等于 target 的位置（左边界）
  • 4.查找最后一个小于等于 target 的位置（右边界）

3. 哈希查找 ⭐⭐⭐⭐（Java 岗位高频结合）

• 原理：通过哈希函数将 key 映射为数组下标，直接定位访问，典型的空间换时间
• Java 绑定考点：HashMap 查找流程 —— 先算哈希值定位桶下标，再通过 hash+equals 匹配节点；哈希冲突用链表解决，JDK8 后链表长度≥8 转红黑树，最坏复杂度从 O (n) 优化为 O (logn)
• 选型注意：写操作频繁、哈希冲突严重的场景，哈希查找性能会下降

💻 面试高频真题 & 核心 Java 代码

题 1：基础二分查找(leetcode 704)

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防整数溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

题 2：搜索旋转排序数组（LeetCode 33，字节 / 阿里高频）

核心思路：旋转后总有一半区间是有序的，判断 target 是否在有序区间内再收缩边界

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        // 左半段有序
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else { // 右半段有序
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

题 3：两数之和(leetcode 1)（哈希查找经典应用）

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            return new int[]{map.get(target - nums[i]), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

⚠️ 面试避坑总结（答出来直接拉开差距）

1. 二分查找不能用在链表上：链表不支持随机访问，二分查找的时间复杂度会退化为 O (n)，失去意义
2. 小数据量没必要用二分：n<100 时，线性查找的实际运行速度和二分差距极小，代码实现更简单
3. 哈希查找的取舍：本质是空间换时间，适合读多写少、对查询延迟要求高的场景
4. 重复元素场景：必须先明确业务要求 —— 返回任意一个、第一个匹配项还是全部匹配项，对应不同的实现方案

💻 核心亮点代码合集（面试手写直接加分）

每段代码都标注了技术亮点细节，避开新手 “玩具代码” 的通病，直击面试官对代码功底的考察点。

1 工业级标准二分查找（零 bug 范式版）

/**
 * 标准二分查找：左闭右闭统一范式，无死循环、无溢出风险
 * 技术亮点：鲁棒性前置校验、防溢出位运算优化、边界逻辑完全自洽
 */
public int binarySearchStandard(int[] nums, int target) {
    // 亮点1：前置空校验，避免空指针/无效循环，体现代码鲁棒性
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0;
    int right = nums.length - 1; // 右闭区间：right指向有效元素下标
    
    // 亮点2：循环条件匹配区间定义：闭区间用 <=，left>right时区间无元素才终止
    while (left <= right) {
        // 亮点3：防溢出核心写法 + 位运算提速
        // 替代 (left+right)/2，规避int最大值相加溢出；>>1 比 /2 底层执行更快
        int mid = left + ((right - left) >> 1);
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            // 亮点4：边界收缩精准：mid已比对过，直接+1跳过，避免重复比对
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

✅ 一句话亮点总结：区间定义、循环条件、边界收缩三者完全统一，从根源杜绝死循环和溢出问题。

2 二分左边界变种（第一个等于 target 的位置）

/**
 * 查找第一个等于目标值的下标，无匹配返回-1
 * 技术亮点：收缩边界逻辑精准、后置合法性校验，覆盖重复元素全场景
 */
public int searchFirstEqual(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        // 核心：相等时不返回，继续向左收缩右边界，找更早的匹配项
        if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 亮点：双重后置校验，避免数组越界 + 无匹配场景
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

✅ 一句话亮点总结：所有二分变种的基础模板，掌握后可快速推导右边界、上下界等所有变形题。

3 旋转排序数组查找(leetcode 33)（字节 / 阿里高频题最优解）

/**
 * 旋转有序数组查找，时间复杂度严格O(logn)
 * 技术亮点：利用分段有序性，无需找旋转点，一次二分完成
 */
public int searchRotate(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        
        // 亮点：等号处理边界相等场景，避免单元素、相邻元素的漏判
        if (nums[left] <= nums[mid]) {
            // 左半段有序：判断target是否落在有序区间内
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右半段有序：同理收缩边界
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

✅ 一句话亮点总结：打破 “二分只能用在全有序数组” 的刻板认知，体现对二分思想的深度理解。

4 哈希查找优化版（两数之和(leetcode 1) 工程级实现）

/**
 * 两数之和：哈希查找经典应用，优化底层开销
 * 技术亮点：预设容量避免扩容、一次遍历完成查插，减少哈希计算次数
 */
public int[] twoSumOptimize(int[] nums, int target) {
    int len = nums.length;
    // 亮点1：预设容量+考虑负载因子，避免HashMap扩容重哈希的性能损耗
    Map<Integer, Integer> map = new HashMap<>((int)(len / 0.75f) + 1);
    
    for (int i = 0; i < len; i++) {
        int complement = target - nums[i];
        // 亮点2：先查后插，一次遍历完成，避免重复哈希计算
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

✅ 一句话亮点总结：从 Java 集合底层原理优化代码，体现对 HashMap 的掌握深度，区别于新手写法。

🎯 技术难点与解决方案对照表

整理了查找类算法面试中 6 个核心高频难点，对应标准解决方案和面试加分表达，答出来直接体现实战经验。

技术难点	问题本质	解决方案	面试加分话术
二分查找边界混乱，频繁出现死循环、漏匹配元素	区间定义（左闭右闭 / 左闭右开）与循环条件、边界收缩逻辑不统一	统一采用左闭右闭范式：循环条件固定left <= right，边界收缩固定left=mid+1/right=mid-1，所有变种基于该范式扩展	“我写二分一定会先明确区间定义，用统一的闭区间范式，能从根源上避免 90% 的边界 bug”
mid 计算整数溢出，大数据量下出现异常结果	Java int 为有符号 32 位，(left+right)超过 2^31-1 时溢出为负数，数组下标直接报错	采用left + (right - left) / 2，进阶可用位运算left + ((right - left) >> 1)，性能更优	“手写二分我不会用 (left+right)/2，会用防溢出写法，这是工业级代码的基本要求”
重复元素场景下，无法精准定位第一个 / 最后一个匹配项	基础二分找到任意匹配就返回，无法控制边界范围	匹配时不直接返回，向目标方向收缩边界；循环结束后校验边界合法性，判断是否存在匹配	“处理重复元素的二分变种，核心是‘收缩边界 + 后置校验’，所有变种都可以套这个思路”
部分有序数组（旋转数组、山峰数组）无法直接用二分	不满足二分查找 “全局有序” 的前置条件	利用数组 “分段有序” 的特性，每次先判断哪一段有序，再判断目标是否在有序区间内，全程保持 O (logn) 复杂度	“旋转数组不用先找旋转点，直接通过 mid 和左右端点比对，就能确定有序区间，一次二分就能完成”
哈希查找在高冲突场景下性能退化，甚至退化为 O (n)	哈希函数分布不均、冲突链表过长，查询效率线性下降	1. 用扰动函数打散哈希值，减少冲突概率；2. 链表长度超过阈值转红黑树，最坏复杂度降为 O (logn)；3. 合理设置初始容量减少扩容重哈希	“JDK8 的 HashMap 用红黑树解决了高冲突下的性能退化问题，同时预设容量也能减少很多不必要的性能损耗”
亿级大数据量下，内存装不下全量数据，无法直接内存查找	数据量超过内存上限，无法加载到数组 / 哈希表中执行查找	采用分层查找思想：外存分块有序存储，内存只加载索引块；先通过二分定位数据块，再在块内做精细查找，对应工程落地就是数据库 B + 树索引的设计思路	“超大数据量的查找本质是‘空间换时间 + 分层思想’，和数据库 B + 树索引的设计逻辑是完全一致的”

真实面试模拟

真实面试模拟

面试官：

我看你简历上写了熟悉常用算法，那咱们先聊聊查找吧。你能简单说一下，你都知道哪些查找算法？各自的时间复杂度大概什么量级？ 😊

候选人：

好的面试官。我按数据结构分几类说吧，顺手帮您画个对比表，更直观：

算法	平均时间	最坏时间	空间	适用条件
顺序查找	O(n)	O(n)	O(1)	小数据或链表
二分查找	O(log n)	O(log n)	O(1)	有序数组
哈希查找	O(1)	O(n)	O(n)	键值对，内存足
二叉搜索树	O(log n)	O(n)	O(n)	动态数据，可能退化
红黑树/AVL	O(log n)	O(log n)	O(n)	平衡，Java TreeMap
B+树	O(log n)	O(log n)	O(n)	磁盘IO，数据库索引

它们的脉络大概是这样的：

面试官：

嗯，表画得挺清楚。那写个标准二分查找吧，用 Java，别翻车啊。 😏

候选人：

好。我一般用左闭右开 [left, right) 这个区间定义，边界控制不容易乱：

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length; // 右开
    while (left < right) {
        int mid = left + (right - left) / 2; // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid; // 因为右开，所以直接等于mid
    }
    return -1;
}

核心就是守住 [left, right) 这个循环不变量，每次缩小区间时绝不破坏它。

面试官：

不错。那把题目变一下：有序数组里有重复值，让你找第一个等于 target 的下标，怎么改？ 🤔

候选人：

改动很小，关键在于 等于 target 时不能直接返回，要继续向左压缩右边界。

逻辑变成：if (nums[mid] >= target) right = mid; 这样即使找到 target，也会把 right 移到 mid，缩左半区。最后检查 left 位置的值：

int firstEqual(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    // 防越界并判断是否真的等于target
    if (left < nums.length && nums[left] == target) return left;
    return -1;
}

如果问最后一个等于，就把条件改成 nums[mid] <= target 时 left = mid + 1，最后返回 left - 1。

至于旋转排序数组的查找（LeetCode 33），我会看 mid 落在左侧有序段还是右侧有序段，再用有序那半段确定 target 在不在里面，从而移动左右边界。

面试官：

搞定了二分，那哈希查找你平时用得多。讲讲 HashMap 是怎么解决哈希冲突的？为什么扩容要设计成 2 的幂？ 🧐

候选人：

JDK 1.8 的 HashMap 用的是拉链法，桶里挂链表；当链表长度 ≥8 且数组长度 ≥64 时，链表会树化成红黑树，防止退化成 O(n)。

扩容用 2 的幂主要是为了用位运算代替取模——(n-1) & hash 等价于 hash % n，效率极高。而且扩容时数据迁移特别快：旧桶里的元素，要么留在原索引 j，要么去 j + oldCap，刚好利用高位 bit 分流。✨

面试官：

再给你个场景题：千万级用户 ID，想快速判断一个 ID 是否已存在，你会怎么设计？内存方面怎么权衡？ 🧠

候选人：

我会分三层来答：

1. 内存够用：直接 HashSet，O(1) 查找，简单粗暴。💪
2. 内存吃紧：改用 BitMap。一个 bit 代表一个 ID，假设 ID 是 32 位整型，范围 0~2³¹ 大约需要 2³¹ bit = 256MB，如果用 2³⁰ 左右的范围可能 128MB 就能搞定，按一亿算也就大约 12.5MB，非常省。
3. 内存极小但能容忍误判：上 布隆过滤器。多个哈希函数对 ID 置位，判断时说“不存在”一定正确，说“存在”可能有小概率误判，很适合缓存穿透、黑名单这类场景。

数据量再大到跨机器，就考虑 一致性哈希 + 分布式表 了。

面试官：

MySQL 索引底层的 B+ 树，为什么不用红黑树或者哈希呢？ 🌳

候选人：

因为数据库索引是存在磁盘上的，瓶颈在 IO 次数，而不是单纯的 CPU 比较次数。

• 红黑树是二叉树，树高 O(log n)，千万级数据树高会达到 20+ 层，一次查询可能几十次随机磁盘 IO，扛不住。
• 哈希虽然 O(1)，但无法支持范围查询 BETWEEN，也不能排序。
• B+ 树多叉，一个节点存几百个键，所以树高极低，通常 3~4 层就能装下上千万数据，IO 次数降下来了。而且叶子节点是双向链表，天然适合范围扫描和排序。🎯

面试官：

挺好，最后帮你把今天的代码亮点和核心难点都盘一盘，就当是总结。 📝

🔥 核心代码 & 技术亮点

1. 标准二分(leetcode 704)（左闭右开模板）

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length; // 右开
    while (left < right) {
        int mid = left + (right - left) / 2; // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid; // 右开，直接缩到 mid
    }
    return -1;
}

💡 亮点：循环不变量 的意识——始终维护 [left, right) 区间，所有边界修改都遵守这一定义，彻底告别死循环。

2. 二分变体：找第一个等于 target

int firstEqual(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid; // 相等也不停，向左缩
        else left = mid + 1;
    }
    if (left < nums.length && nums[left] == target) return left;
    return -1;
}

💡 亮点：只改动一个条件判断，就能实现“找左边界”，将 “等于” 并入 “大于” 分支，是二分变体的精髓。

3. 旋转排序数组查找（LeetCode 33）

int searchRotated(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] >= nums[left]) { // mid 在左侧有序段
            if (target >= nums[left] && target < nums[mid]) right = mid;
            else left = mid + 1;
        } else { // mid 在右侧有序段
            if (target > nums[mid] && target <= nums[right-1]) left = mid + 1;
            else right = mid;
        }
    }
    return -1;
}

💡 亮点：通过 mid 与 left 的值判断有序区间，再在有序区间内用普通二分逻辑，将 O(n) 优化为 O(log n)。

4. HashMap 扩容迁移的巧妙设计

// JDK 源码精华（伪代码）
Node<K,V> loHead = null, loTail = null; // 留在原索引
Node<K,V> hiHead = null, hiTail = null; // 去新索引
for (Node<K,V> e : oldTab[j]) {
    if ((e.hash & oldCap) == 0) { // 高位 bit 为 0
        // 加入 lo 链表
    } else {
        // 加入 hi 链表
    }
}
newTab[j] = loHead;
newTab[j + oldCap] = hiHead;

💡 亮点：利用 (e.hash & oldCap) 判断元素在新数组的位置，避免了重新计算 hash，只需要一次位运算，扩容效率极高。

🧩 场景技术难点与解决方案

难点	出现场景	解决方案
二分边界死循环	手写二分查找时频繁出现	统一区间定义（推荐左闭右开），坚持循环不变量，mid 计算防溢出
旋转数组判断逻辑	部分有序的查找	通过 nums[mid] 与 nums[left] 比较确定有序区间，分情况处理
哈希冲突导致链表退化	高并发或 key 设计不合理时，HashMap 退化成 O(n)	链表长度 ≥8 且数组长度 ≥64 时转红黑树；使用均匀分布的 hashCode
千万级数据内存不够	大基数 ID 去重或存在判断	BitMap 用 1 bit 标记，布隆过滤器容忍少量误判，或选择分布式方案
磁盘 IO 瓶颈下的范围查找	数据库索引查找	使用 B+ 树替代红黑树，多叉降低树高，叶子链表支持范围扫描
并发环境下的查找数据结构选择	线程安全查找	ConcurrentHashMap 采用分段锁或 CAS；跳表（ConcurrentSkipListMap）适合高并发有序查找

面试官：

今天就到这里吧。看得出你的基础知识很扎实，工程落地也有自己的思考。期待下一轮你能接着聊排序和图算法。 👏

候选人：

谢谢面试官，回去我再把跳表和 LSM 树的那部分也补上，下次见！ 😄