掌握顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。

顺序查找：

基本思想：从数据的一端开始，依次比较每一个数据项，直到找到或搜索完整个数据集。

算法实现：顺序查找的实现很简单，就是一个 for 循环，从头到尾依次比较每一个数据项。

时间性能分析：最好的情况是在第一个数据项就找到了，此时查找次数为 1。最坏的情况是要查找整个数据集，此时查找次数为 n。平均查找次数为 (n+1)/2。

折半查找：

基本思想：在有序数据集中，先查找中间位置的数据项，如果和要查找的数据相等，则查找成功；如果要查找的数据大于中间位置的数据，则在后半段继续查找；如果要查找的数据小于中间位置的数据，则在前半段继续查找，直到找到数据或者查找完整个数据集。

算法实现：折半查找的实现是通过递归或者循环来实现的，具体实现方法可以参考以下代码：

def binary_search(data_list, target):
    low = 0
    high = len(data_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if data_list[mid] == target:
            return True
        elif data_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

时间性能分析：折半查找的最坏情况是要查找整个有序数据集，此时查找次数为 log2(n)。平均查找次数为 log2(n+1)-1。

二叉排序树：

基本思想：二叉排序树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，右子树中的所有节点的值都大于根节点的值。在查找数据时，从根节点开始比较，如果要查找的数据小于根节点的值，则在左子树中继续查找；如果要查找的数据大于根节点的值，则在右子树中继续查找，直到找到数据或者查找完整个数据集。

算法实现：二叉排序树的查找可以通过递归或者循环来实现，具体实现方法可以参考以下代码：

class TreeNode:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None
        self.right_child = None

def insert_node(root, value):
    if root is None:
        root = TreeNode(value)
    else:
        if value < root.value:
            root.left_child = insert_node(root.left_child, value)
        elif value > root.value:
            root.right_child = insert_node(root.right_child, value)
    return root

def search_node(root, value):
    if root is None:
        return False
    elif root.value == value:
        return True
    elif value < root.value:
        return search_node(root.left_child, value)
    else:
        return search_node(root.right_child, value)

时间性能分析：二叉排序树的平均查找长度与树的形状有关，最好情况是树的高度为 log2(n)，此时平均查找长度为 log2(n+1)-1；最坏情况是树的高度为 n，此时平均查找长度为 (n+1)/2。因此，二叉排序树的性能取决于数据的插入顺序，如果数据是随机插入的，则树的高度会接近 log2(n)，性能较好；如果数据是有序插入的，则树的高度为 n，性能较差。