讨论3.1 黄金分割查找？
在二分查找中，我们是取mid等于left和right的中间值，即用等分的方法进行查找.
那为什么一定要等分呐？能不能进行“黄金分割”？也就是mid=left+0.618(right-left),当然mid要取整数。如果这样查找，时间复杂性是多少？也许你还可以编程做个试验，比较一下二分法和“黄金分割”法的执行效率。
黄金分割查找（Golden Section Search）是一种基于斐波那契数列的查找算法，它可以将查找区间划分为两个部分，并选择其中一个部分的中间点作为查找点。这种查找算法的时间复杂度为O(log n)，与二分查找相同。
在黄金分割查找中，我们首先将查找区间划分为两个部分，其中一个部分的长度为黄金比例（约为0.618）与另一个部分的长度之和。然后，我们在其中一个部分的中间点进行查找。如果目标元素在这个中间点位置上，则查找结束。否则，我们将根据目标元素与中间点的相对位置来确定下一步的查找区间。
相比于二分查找，黄金分割查找的不同之处在于它将查找区间划分为两个部分，而不是简单地等分。这种划分方式可以使得查找更加细致，从而提高查找的精度和效率。
下面是一个简单的C语言实现黄金分割查找的示例代码：
c
#include <stdio.h>
#include <math.h>
double golden_section_search(double a, double b, double x) {
double mid, fmid;
int n = 0;
while (fabs(a - b) > 1e-6) { // 判断区间是否足够小
n++;
mid = a + 0.618 * (b - a); // 计算中间点
fmid = mid - x; // 计算中间点处的值
if (fmid < 0) { // 如果目标函数在左半部分，则将右边界缩小为mid
b = mid;
} else { // 如果目标函数在右半部分，则将左边界缩小为mid+b-a
a = mid + b - a;
}
}
printf("Number of iterations: %d\n", n); // 输出迭代次数
return mid; // 返回中间点处的值
}
这个示例代码实现了一个黄金分割查找函数golden_section_search，它接受三个参数：查找区间的左端点a、右端点b和目标函数在区间内的值x。函数使用while循环进行迭代，直到区间的长度足够小（小于1e-6）为止。在每次迭代中，函数计算中间点的位置和目标函数在中间点处的值fmid，然后根据fmid的正负来确定下一步的查找区间。最后，函数返回中间点处的值。
树
树（Tree）是一种非线性的数据结构，通常由节点（Nodes）和边（Edges）组成。树可以表示层次结构，其中节点表示实体，边表示节点之间的关系。
树的基本特点是：
有且仅有一个根节点（Root Node），没有父节点。
其他节点可以有零个或多个子节点（Child Nodes），每个子节点只能有一个父节点。
树中的节点不能有环路（Cycle），即从某个节点出发沿着边不能回到出发节点。
树中的边没有权重，即节点之间的关系没有大小之分。
树有很多种，如二叉树（Binary Tree）、完全二叉树（Complete Binary Tree）、满二叉树（Full Binary Tree）、平衡二叉树（Balanced Binary Tree）、红黑树（Red-Black Tree）等。
树的应用非常广泛，如文件系统、图形学、人工智能、数据压缩等。在计算机科学中，树是常见的数据结构之一，也是许多算法的基础。
森林
在数据结构中，森林是一个由多个不相交的树组成的集合。每个树都由一个根节点和若干个子树组成，而每个子树也是一个由根节点和若干个子树组成的树。森林中的树之间没有直接的关联，它们之间的关系是通过森林这个集合来定义的。
森林常用于表示一个有多个子问题的复杂问题，每个子问题都可以被视为一棵独立的树。通过将所有子问题的解组合起来，可以获得复杂问题的解。
在数据结构中，森林通常用数组或链表来实现。在数组实现中，每个树都存储在一个连续的内存块中，而树的节点则按照树的深度（从根节点到叶节点的路径长度）排列。在链表实现中，每个树都由一个头节点和若干个子节点组成，子节点通过指针与它们的父节点相连。
森林是一种由多个不相交的树组成的集合，常用于表示一个有多个子问题的复杂问题。
在数据结构中，森林是一个由多个不相交的树组成的集合。每个树都由一个根节点和若干个子树组成，而每个子树也是一个由根节点和若干个子树组成的树。森林中的树之间没有直接的关联，它们之间的关系是通过森林这个集合来定义的。
森林常用于表示一个有多个子问题的复杂问题，每个子问题都可以被视为一棵独立的树。通过将所有子问题的解组合起来，可以获得复杂问题的解。
在数据结构中，森林通常用数组或链表来实现。在数组实现中，每个树都存储在一个连续的内存块中，而树的节点则按照树的深度（从根节点到叶节点的路径长度）排列。在链表实现中，每个树都由一个头节点和若干个子节点组成，子节点通过指针与它们的父节点相连。
总之，森林是一种由多个不相交的树组成的集合，常用于表示一个有多个子问题的复杂问题。
