1. 基本概念

二分查找是一种在 有序数组（或者满足单调性的集合/区间）中查找目标值的算法。
核心思想是：

• 每次把搜索范围减半；
• 根据目标值和中间值的比较，决定往左半边还是右半边继续查找。

时间复杂度：

• 每次都缩小一半 → O(log n)
  空间复杂度：
• 迭代版 O(1)，递归版 O(log n)（栈深度）

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

输出所有的解法结果。

示例:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。

• 节点的右子树只包含大于当前节点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

大家好，我是老马。

今天我们一起来学习一下数组密切相关的二分查找算法。

主要知识

二分查找算法需要拆分下面几个部分：

1. 入门介绍

2. 题目练习（按照算法思想分类）

3. 梳理对应的 sdk 包

4. 应用实战

入门介绍

二分查找法（Binary Search）是算法中非常经典且高效的一种查找方法，适用于有序集合。

下面是对它的详细介绍、各种变体、实战技巧与常见坑点，适合用于 LeetCode 刷题和算法面试准备。

大家好，我是老马。

今天我们一起来学习一下数组密切相关的三分查找算法。

主要知识

三分查找算法需要拆分下面几个部分：

1. 入门介绍

2. 题目练习（按照算法思想分类）-- 实际有哪些应用场景？可以解决哪些实际的问题

3. 和已有知识的关系，比如对比二分查找

4. 梳理对应的 sdk 包

5. 应用实战

三分查找介绍

🔍 什么是三分查找（Ternary Search）？

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析：

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时，需要n+1次比较，时间复杂度为O(n);

所以，顺序查找的时间复杂度为O(n)。

代码实现