说明1：假定本次实验中要查找的记录只有一个数据项，且该数据项为整数，用数组来存储记录集合。 说明2：读者在上机实验时, 可参考实验八中的基本函数，随机生成测试数据集。 说明3：二分查找（折半查找）算法需要对随机生成的数据集先排序，然后再查找。算法设计： 1．实现线性表的二分（折半）查找算法。 2．实现树表的二叉排序树的创建、插入、删除、查找算法。 3*．实现散列表的散列查找方法。

1. 实现线性表的二分（折半）查找算法

线性表的二分查找算法要求线性表中的元素必须是有序的。具体实现步骤如下：

1. 首先确定待查找的区间的左右边界，即 low 和 high，其中 low 初始值为 0，high 初始值为 n-1，n 为数组的长度。
2. 计算中间位置 mid，即 mid = (low + high) / 2。
3. 比较要查找的值 key 和 mid 位置上的值 arr[mid] 的大小。如果 key 等于 arr[mid]，则查找成功，返回 mid；否则，如果 key 小于 arr[mid]，则在左半边继续查找；如果 key 大于 arr[mid]，则在右半边继续查找。
4. 重复执行第二步和第三步，直到找到 key，或者 low 大于 high，此时查找失败，返回 -1。

以下是线性表的二分查找算法的 Python 代码：

def binary_search(arr, key):
    n = len(arr)
    low, high = 0, n-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return -1

2. 实现树表的二叉排序树的创建、插入、删除、查找算法

二叉排序树（Binary Search Tree，简称 BST）是一种基于二叉树的数据结构，它的每个节点都包含一个关键字和两个子树，其中左子树上所有节点的关键字都小于它的父节点的关键字，右子树上所有节点的关键字都大于它的父节点的关键字。

二叉排序树的创建、插入、删除和查找算法的具体实现如下：

创建二叉排序树：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def create_bst(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    for i in range(1, len(arr)):
        insert_bst(root, arr[i])
    return root

插入节点：

def insert_bst(root, val):
    if not root:
        root = TreeNode(val)
        return
    if val < root.val:
        if not root.left:
            root.left = TreeNode(val)
        else:
            insert_bst(root.left, val)
    elif val > root.val:
        if not root.right:
            root.right = TreeNode(val)
        else:
            insert_bst(root.right, val)

删除节点：

def delete_bst(root, val):
    if not root:
        return root
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else:
        # 如果要删除的节点只有一个子节点或者没有子节点
        if not root.left:
            temp = root.right
            root = None
            return temp
        elif not root.right:
            temp = root.left
            root = None
            return temp
        # 如果要删除的节点有两个子节点
        temp = min_value_node(root.right)
        root.val = temp.val
        root.right = delete_bst(root.right, temp.val)
    return root

def min_value_node(node):
    while node.left:
        node = node.left
    return node

查找节点：

def search_bst(root, val):
    if not root:
        return None
    if root.val == val:
        return root
    elif root.val > val:
        return search_bst(root.left, val)
    else:
        return search_bst(root.right, val)

3. 实现散列表的散列查找方法

散列表（Hash Table）是一种基于数组的数据结构，它利用散列函数（Hash Function）将关键字映射到数组中的一个位置，以实现快速的查找、插入和删除操作。

散列查找方法的具体实现步骤如下：

1. 根据给定的关键字 key，计算出它在数组中的位置，即 hash(key)。
2. 如果该位置上没有元素，则查找失败，返回 -1。
3. 如果该位置上的元素的关键字等于 key，则查找成功，返回该元素的下标。
4. 如果该位置上的元素的关键字不等于 key，则继续查找下一个位置，直到找到 key，或者遇到空位置，此时查找失败，返回 -1。

以下是散列表的散列查找方法的 Python 代码：

def hash_func(key):
    return key % 10

def hash_search(arr, key):
    n = len(arr)
    pos = hash_func(key)
    while arr[pos] and arr[pos] != key:
        pos = (pos + 1) % n
    if not arr[pos]:
        return -1
    else:
        return pos