线性表查找通关攻略：三板斧（顺序/二分/分块查找）

📝 写在前面

上两期我们聊了排序，今天来聊聊查找。查找就像"大海捞针"，但我们可以用不同的策略让捞针变得更快。

查找算法的核心：如何快速在数据集合中找到目标元素？

今天要介绍的线性表查找三兄弟：

• 顺序查找：无脑遍历，简单但慢

• 二分查找：每次砍掉一半，快但要求有序

• 分块查找：折中方案，既有速度又不需要全有序

阅读指南：每个算法包含👇

• 生活比喻：一句话记住核心思想

• 算法可视化：算法流程图

• 代码实现：带详细注释

• LeetCode实战：用真题巩固理解

一、三兄弟对比总览

二、顺序查找（Sequential Search）—— 最朴素的找法

🎯 一句话记住

就像在书里一页一页翻找你要的那一页。

🤔 核心思想

从表的一端开始，逐个比较每个元素，直到找到目标或遍历完整个表。

举个栗子：在 [5, 2, 7, 1, 9, 3] 中找 7

• 看第1个：5 ≠ 7

• 看第2个：2 ≠ 7

• 看第3个：7 == 7 ✓ 找到，返回索引2

✨ 优化技巧：监视哨

在数组末尾放一个"哨兵"（目标值），这样就不用在循环里每次都判断是否越界，能提升一点效率。

📊 算法流程图

💻 代码实现

/**
* 顺序查找（基础版）
* @param {number[]} arr 待查找数组
* @param {number} target 目标值
* @returns {number} 目标索引，未找到返回-1
*/
function sequentialSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i; // 找到了
}
}
return -1; // 没找到
}

/**
* 顺序查找（监视哨优化版）
* 原理：把target放在数组末尾，省去每次判断i<arr.length
*/
function sequentialSearchWithSentinel(arr, target) {
// 复制数组，避免修改原数组
const temp = […arr];
temp.push(target); // 添加监视哨

let i = 0;
while (temp[i] !== target) {
i++;
}

// 如果i到了最后一个位置（监视哨位置），说明没找到
return i === temp.length – 1 ? -1 : i;
}

// 测试
const arr = [5, 2, 7, 1, 9, 3];
console.log(sequentialSearch(arr, 7)); // 2
console.log(sequentialSearch(arr, 8)); // -1

🏆 LeetCode实战：搜索插入位置（顺序查找版）

题目：LeetCode 35. 搜索插入位置

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

思路分析： 虽然这道题最优解是二分查找（O(log n)），但作为顺序查找的练习，我们可以先写个顺序查找版本理解题意。

解题代码：

/**
* @param {number[]} nums 排序数组
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
// 顺序查找：找到第一个大于等于target的位置
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) {
return i;
}
}
// 如果所有数都小于target，插在最后
return nums.length;
};

时间复杂度：O(n) 空间复杂度：O(1)

虽然是O(n)，但正好体现了顺序查找的特点：简单直观，对数据无要求。

三、二分查找（Binary Search）—— 高效的杀手锏

🎯 一句话记住

就像猜数字游戏：每次猜中间，对方说"大了"或"小了"，立马排除一半！

🤔 核心思想

在有序数组中，每次取中间元素与目标比较：

• 相等 → 找到了

• 目标 < 中间值 → 在左半部分继续找

• 目标 > 中间值 → 在右半部分继续找

举个栗子：在 [1, 3, 5, 7, 9, 11, 13] 中找 9

• 中间是7，9>7 → 右半部分 [9,11,13]

• 中间是11，9<11 → 左半部分 [9]

• 中间是9，找到了。

📊 算法流程图

💻 代码实现

/**
* 二分查找（非递归版本）
* @param {number[]} arr 有序数组（升序）
* @param {number} target
* @returns {number} 目标索引，未找到返回-1
*/
function binarySearch(arr, target) {
let left = 0;
let right = arr.length – 1;

while (left <= right) {
// 计算中间位置（避免整数溢出）
const mid = left + Math.floor((right – left) / 2);

if (arr[mid] === target) {
return mid; // 找到了
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右边
} else {
right = mid – 1; // 目标在左边
}
}

return -1; // 没找到
}

/**
* 二分查找（递归版本）
*/
function binarySearchRecursive(arr, target, left = 0, right = arr.length – 1) {
if (left > right) return -1;

const mid = left + Math.floor((right – left) / 2);

if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid – 1);
}
}

// 测试
const sortedArr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedArr, 9)); // 4
console.log(binarySearch(sortedArr, 2)); // -1

🏆 LeetCode实战：在排序数组中查找元素的第一个和最后一个位置

题目：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 

题目描述：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。要求 O(log n) 时间复杂度。

思路分析： 这是二分查找的变体题，需要找左右边界：

• 找左边界：当 nums[mid] == target 时，不返回，而是把 right 移到 mid-1，继续向左找

• 找右边界：当 nums[mid] == target 时，把 left 移到 mid+1，继续向右找

解题代码：

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
const findLeft = () => {
let left = 0, right = nums.length – 1;
let result = -1;

while (left <= right) {
const mid = left + Math.floor((right – left) / 2);

if (nums[mid] === target) {
result = mid;
right = mid – 1; // 继续向左找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return result;
};

const findRight = () => {
let left = 0, right = nums.length – 1;
let result = -1;

while (left <= right) {
const mid = left + Math.floor((right – left) / 2);

if (nums[mid] === target) {
result = mid;
left = mid + 1; // 继续向右找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return result;
};

return [findLeft(), findRight()];
};

// 测试
console.log(searchRange([5,7,7,8,8,10], 8)); // [3, 4]

🏆 LeetCode实战：搜索旋转排序数组

题目：LeetCode 33. 搜索旋转排序数组 

题目描述：整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k 上进行了旋转。给你旋转后的数组和一个目标值 target，如果存在返回下标，否则返回 -1。要求 O(log n) 时间复杂度。

思路分析： 这是二分查找的经典变体题。虽然数组被旋转了，但我们可以利用"总有一半是有序的"这个特点：

解题代码：

/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let left = 0, right = nums.length – 1;

while (left <= right) {
const mid = left + Math.floor((right – left) / 2);

if (nums[mid] === target) {
return mid;
}

// 判断哪一半是有序的
if (nums[left] <= nums[mid]) { // 左半部分有序
if (nums[left] <= target && target < nums[mid]) {
right = mid – 1; // target在左边有序区间
} else {
left = mid + 1; // target在右边
}
} else { // 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // target在右边有序区间
} else {
right = mid – 1; // target在左边
}
}
}

return -1;
};

// 测试
console.log(search([4,5,6,7,0,1,2], 0)); // 4

四、分块查找（Block Search）—— 折中的智慧

🎯 一句话记住

就像图书馆找书：先查索引找到在哪个书架，再在书架上慢慢找。

🤔 核心思想

分块查找是顺序查找和二分查找的折中方案：

举个栗子： 数据： [22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53] 分成三块：

• 块1：22,12,13,8,9,20 → 最大值22

• 块2：33,42,44,38,24,48 → 最大值48

• 块3：60,58,74,49,86,53 → 最大值86

索引表：[(22,0), (48,6), (86,12)] 找38：38>22且38<48 → 在块2 → 在块2内顺序查找

💻 代码实现

/**
* 分块查找
* @param {number[]} arr 原数组（块内无序，但块间有序）
* @param {Array<{max: number, start: number, end: number}>} indexTable 索引表
* @param {number} target
* @returns {number} 目标索引，未找到返回-1
*/
function blockSearch(arr, indexTable, target) {
// 1. 在索引表中查找所在块
let blockIndex = -1;
for (let i = 0; i < indexTable.length; i++) {
if (target <= indexTable[i].max) {
blockIndex = i;
break;
}
}

// 没找到合适的块（可能target比所有块的最大值都大）
if (blockIndex === -1) return -1;

// 2. 在块内顺序查找
const block = indexTable[blockIndex];
for (let i = block.start; i <= block.end; i++) {
if (arr[i] === target) {
return i;
}
}

return -1;
}

/**
* 构建索引表（假设每块大小固定）
* @param {number[]} arr 原数组
* @param {number} blockSize 每块大小
* @returns {Array<{max: number, start: number, end: number}>}
*/
function buildIndexTable(arr, blockSize) {
const indexTable = [];
const n = arr.length;

for (let i = 0; i < n; i += blockSize) {
const start = i;
const end = Math.min(i + blockSize – 1, n – 1);

// 找块内最大值
let max = -Infinity;
for (let j = start; j <= end; j++) {
max = Math.max(max, arr[j]);
}

indexTable.push({ max, start, end });
}

return indexTable;
}

// 测试
const data = [22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53];
const indexTable = buildIndexTable(data, 6);
console.log(indexTable);
// 输出: [
// { max: 22, start: 0, end: 5 },
// { max: 48, start: 6, end: 11 },
// { max: 86, start: 12, end: 17 }
// ]

console.log(blockSearch(data, indexTable, 38)); // 9
console.log(blockSearch(data, indexTable, 100)); // -1

🏆 LeetCode实战：搜索二维矩阵（分块思想）

题目：LeetCode 74. 搜索二维矩阵

题目描述：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列

• 每行的第一个整数大于前一行的最后一个整数

思路分析： 这个矩阵可以看作是一个"分块有序"的结构：

• 每行是一个块，块内有序

• 块间有序（下一行的第一个 > 上一行的最后一个）

• 可以用两次二分：第一次找行，第二次在行内找

解题代码：

/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
const m = matrix.length;
const n = matrix[0].length;

// 1. 找可能在哪一行（类似索引表查找）
let top = 0, bottom = m – 1;
while (top <= bottom) {
const midRow = top + Math.floor((bottom – top) / 2);

if (matrix[midRow][0] <= target && target <= matrix[midRow][n – 1]) {
// 2. 在这一行内二分查找
let left = 0, right = n – 1;
while (left <= right) {
const mid = left + Math.floor((right – left) / 2);
if (matrix[midRow][mid] === target) {
return true;
} else if (matrix[midRow][mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return false;
} else if (target < matrix[midRow][0]) {
bottom = midRow – 1;
} else {
top = midRow + 1;
}
}

return false;
};

五、三兄弟对比总结

额外补充：面试常见问题

🎯 下期预告

下一期我们将进入树表查找的世界：二叉搜索树、平衡二叉树、红黑树——从线性结构到树形结构的进化！

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发！有问题欢迎在评论区讨论～