查找算法

• 线性查找：O (n)，适用于无序数据。
• 二分查找：O (log n)，要求数据有序（数组存储），无序则完全不可用。
• 哈希查找：O (1)（平均），利用哈希函数映射，需处理冲突（开放寻址法、链地址法）。但要求以哈希表存储数据，数组处理为哈希表的时间是O（n）
• 树结构查找：BST 查找 O (h)，平衡树查找 O (log n)。

二分查找

知识点概述

二分查找在有序数组中将搜索区间对半缩小，时间复杂度为 $O(\log n)$。

常见考点

• 左右边界
• 单调性与二分答案
• 变体模板
• 二分划分（如中位数问题）

经典题目

困难

• 4. 寻找两个正序数组的中位数 - 二分划分思想