搜索

• 定义：
  • 搜索算法（searching algorithm）用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素

分类：

• 暴力搜索
• 自适应搜索

暴力搜索：

• 思路：遍历数据结构的每个元素
• 遍历策略：
  • 线性搜索：适用于数组和链表
  • 广度、深度优先搜索：适用于树和图
• 优缺点：
  • 优点：简单且通用性好，无须对数据做预处理和借助额外的数据结构
  • 缺点：时间复杂度为$O(n)$

二分查找

定义：

• 二分查找（binary search）是一种基于分治策略的高效搜索算法。
• 它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

具体操作：

1. 先初始化指针 $i = 0$ 和 $j = n - 1$ ，分别指向数组首元素和尾元素，代表搜索区间 $[0, n - 1]$
2. 计算中点索引 $m = \lfloor {(i + j) / 2} \rfloor$ （其中 $\lfloor \: \rfloor$ 表示向下取整操作）
3. 判断 nums[m] 和 target 的大小关系，分为以下三种情况：
   1. 当 nums[m] < target 时，说明 target 在区间 $[m + 1, j]$ 中，因此执行 $i = m + 1$ 。
   2. 当 nums[m] > target 时，说明 target 在区间 $[i, m - 1]$ 中，因此执行 $j = m - 1$ 。
   3. 当 nums[m] = target 时，说明找到 target ，因此返回索引 $m$ 。
4. 重复2、3步骤，一直未找到元素，则搜索区间缩小为空。此时返回 $-1$ 。
5. 注意项：由于 $i$ 和 $j$ 都是 int 类型，因此 $i + j$ 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式 $m = \lfloor {i + (j - i) / 2} \rfloor$ 来计算中点

作用：

• 用于树、图的遍历

广度优先：

• 广度优先遍历通常借助队列来实现。队列遵循先进先出的规则，而广度优先遍历则遵循逐层推进的规则
• 代码实现（树）：

  /* 层序遍历 */
  func levelOrder(root *TreeNode) []any {
      // 初始化队列，加入根节点
      queue := list.New()
      queue.PushBack(root)
      // 初始化一个切片，用于保存遍历序列
      nums := make([]any, 0)
      for queue.Len() > 0 {
          // 队列出队
          node := queue.Remove(queue.Front()).(*TreeNode)
          // 保存节点值
          nums = append(nums, node.Val)
          if node.Left != nil {
              // 左子节点入队
              queue.PushBack(node.Left)
          }
          if node.Right != nil {
              // 右子节点入队
              queue.PushBack(node.Right)
          }
      }
      return nums
  }

搜索树查找

• 直接使用搜索树的节点有序、节点大小关系等特性
• 本质思想根二分查找一致，通过有序的先验条件，快速排除1/2、1/M的节点，M为树的阶数

过程：

• 基于搜索树搜索：
  • 二叉搜索树：比较target和节点值大小；小于节点，继续找左子树，大于节点，继续找右子树；相等则找到，或者访问到叶子节点也未找到。
  • B树：比较target和节点值大小；根据值所在区间，到对应子树继续查找；如果节点中有根target相等，则可以在该节点找到target信息，或者访问到叶子节点也未找到。
  • B+树：比较非叶子节点和target，根据值所在区间，到对应子树继续查找；因为只有叶子节点存数据，一直要找到叶子节点，才能找到target的具体信息