跳到主要内容

搜索✅

搜索算法是计算机科学中的核心概念，用于在数据结构中查找特定元素。本章涵盖二分查找和树结构查找等重要搜索技术。

// 实现二分查找算法，在有序数组中查找目标值
// 输入：有序数组 [1, 3, 5, 6, 8, 10, 15]，目标值 5
// 输出：目标值的索引 2，不存在返回 -1
function binarySearch(nums, target) {
  // 请实现二分查找逻辑
}
答案

核心概念​

二分查找是一种高效的搜索算法，适用于已排序的数组。通过每次将搜索范围缩小一半来快速定位目标元素。

算法思路​

  1. 设置双指针：左指针指向数组开始，右指针指向数组结束
  2. 计算中点：mid = (left + right) / 2
  3. 比较判断：
    • 如果 nums[mid] === target，找到目标，返回索引
    • 如果 nums[mid] < target，目标在右半部分，left = mid + 1
    • 如果 nums[mid] > target，目标在左半部分，right = mid - 1
  4. 重复搜索：直到找到目标或搜索区间为空

时间复杂度: O(log n)
空间复杂度: O(1)

示例实现​

/**
 * 二分查找
 * @param {number[]} nums - 有序数组
 * @param {number} target - 目标值
 * @returns {number} 目标值索引，不存在返回-1
 */
function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}

/**
 * 查找第一个大于等于target的位置（左边界）
 */
function searchLeftBound(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return left;
}

/**
 * 查找最后一个小于等于target的位置（右边界）
 */
function searchRightBound(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return right;
}

module.exports = { binarySearch, searchLeftBound, searchRightBound };

Open browser consoleTests

变体应用​

  • 查找左边界: 找到第一个大于等于目标值的位置
  • 查找右边界: 找到最后一个小于等于目标值的位置
  • 旋转数组搜索: 在旋转排序数组中应用二分查找

面试官视角​

该题考察候选人对经典算法的理解和实现能力：

  • 要点清单: 理解二分查找原理；正确处理边界条件；掌握时间空间复杂度；能实现不同变体
  • 加分项: 了解整数溢出问题；掌握查找边界的技巧；能处理重复元素；有实际应用经验
  • 常见失误: 边界条件处理错误；死循环问题；中点计算溢出；不理解查找范围更新

延伸阅读​

树结构查找如何实现？​

// 在树形结构中按ID查找节点
// 输入：树形数组和目标ID
// 输出：找到的节点对象或null
const tree = [
  {
    id: 1,
    name: '根节点1',
    children: [
      { id: 11, name: '子节点1-1', children: [{ id: 111, name: '叶节点' }] }
    ]
  }
];
function findNodeById(tree, id) {
  // 请实现树结构查找逻辑
}
答案

核心概念​

树结构查找是在层次化数据中定位特定节点的过程。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历树结构。

算法策略​

  1. 深度优先搜索（DFS）

    • 递归遍历每个节点及其子节点
    • 优先搜索深度，适合查找单个目标
    • 空间复杂度较低

  2. 广度优先搜索（BFS）

    • 使用队列逐层遍历节点
    • 适合查找最短路径或层次相关问题
    • 能找到离根节点最近的目标

实现要点​

  • 递归终止条件: 当前节点匹配目标或无子节点
  • 遍历子节点: 对每个子节点进行递归搜索
  • 结果返回: 找到目标立即返回，避免无效遍历
  • 空值处理: 检查节点和子节点数组是否存在

示例实现​

/**
 * 在树结构中按ID查找节点
 * @param {Array} tree - 树形数组
 * @param {string|number} id - 要查找的ID
 * @returns {Object|null} 找到的节点或null
 */
function findNodeById(tree, id) {
  if (!tree || tree.length === 0) return null;

  const search = (node) => {
    if (node.id === id) {
      return node;
    }
    
    if (node.children && node.children.length > 0) {
      for (const child of node.children) {
        const result = search(child);
        if (result) {
          return result;
        }
      }
    }
    
    return null;
  };

  for (const root of tree) {
    const result = search(root);
    if (result) {
      return result;
    }
  }

  return null;
}

/**
 * 在树结构中查找满足条件的所有节点
 * @param {Array} tree - 树形数组
 * @param {Function} predicate - 判断函数
 * @returns {Array} 符合条件的节点数组
 */
function findAllNodes(tree, predicate) {
  if (!tree || tree.length === 0) return [];
  
  const results = [];
  
  const search = (node) => {
    if (predicate(node)) {
      results.push(node);
    }
    
    if (node.children && node.children.length > 0) {
      for (const child of node.children) {
        search(child);
      }
    }
  };

  for (const root of tree) {
    search(root);
  }

  return results;
}

/**
 * 在树结构中查找节点的路径
 * @param {Array} tree - 树形数组
 * @param {string|number} id - 要查找的ID
 * @returns {Array|null} 从根到目标节点的路径数组
 */
function findPath(tree, id) {
  if (!tree || tree.length === 0) return null;

  const search = (node, path) => {
    const currentPath = [...path, node];
    
    if (node.id === id) {
      return currentPath;
    }
    
    if (node.children && node.children.length > 0) {
      for (const child of node.children) {
        const result = search(child, currentPath);
        if (result) {
          return result;
        }
      }
    }
    
    return null;
  };

  for (const root of tree) {
    const result = search(root, []);
    if (result) {
      return result;
    }
  }

  return null;
}

module.exports = { findNodeById, findAllNodes, findPath };

Open browser consoleTests

扩展功能​

  • 查找所有匹配节点: 返回满足条件的节点数组
  • 查找节点路径: 返回从根节点到目标节点的完整路径
  • 条件查找: 基于自定义条件函数进行复杂查找
  • 性能优化: 使用索引映射提高大型树结构的查找效率

面试官视角​

该题考察候选人对树结构和搜索算法的理解：

  • 要点清单: 理解树结构遍历；能实现递归和迭代两种方式；处理边界情况；了解时间空间复杂度
  • 加分项: 知道DFS和BFS的适用场景；能优化性能；处理复杂树结构；有实际项目应用
  • 常见失误: 无限递归；未处理空节点；遗漏边界条件；不理解搜索策略差异

延伸阅读​