python实现折半查找并能打印对应的数据项

折半查找，也称为二分搜索，是一种在有序列表或数组中查找特定元素的算法。它通过将目标值与中间元素比较，并根据比较结果决定是在左半部分还是右半部分继续搜索的过程。以下是Python实现折半查找的一个简单示例：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            print(f"找到数据项 {arr[mid]}，索引为 {mid}")
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    print("未找到目标数据项")
    return -1

# 使用示例
sorted_list = [1, 3, 5, 7, 9, 11]
target_to_find = 7
binary_search(sorted_list, target_to_find)

在这个例子中，`binary_search`函数接收一个排序后的列表`arr`和目标值`target`作为参数。如果找到目标值，会打印出该值及其对应的索引；如果没有找到，则返回-1。

相关问题

python实现折半查找并能打印对应的数据项，数据项中蕴含其它元素，如姓名，性别等，依旧可以打印出来

在Python中，折半查找，也称为二分搜索，通常用于已排序的列表或数组中。假设我们有一个包含姓名和性别元组的列表，比如按姓名字母顺序排列，我们可以创建一个函数来执行折半查找，并在找到指定名称时返回其对应的元组。下面是一个简单的例子：

def binary_search(data, target_name):
    low = 0
    high = len(data) - 1
    
    while low <= high:
        mid = (low + high) // 2
        search_item = data[mid]
        
        if search_item[0] == target_name:
            print(f"找到 {search_item[0]}，姓名：{search_item[0]}, 性别：{search_item[1]}")
            return search_item
        elif search_item[0] < target_name:
            low = mid + 1
        else:
            high = mid - 1
            
    print("未找到指定姓名.")
    return None

# 示例数据
data = [("Alice", "女"), ("Bob", "男"), ("Charlie", "男"), ("David", "女")]
target_name = "Alice"

binary_search(data, target_name)

在这个例子中，`binary_search`函数接受一个已经排好序的元组列表`data`和目标名字`target_name`作为输入。如果找到匹配的姓名，它将打印出姓名和性别；如果没有找到，则会显示未找到的信息。

对有序表进行折半查找判定树

### 关于有序表进行折半查找判定树的概念

对于长度为 n 的有序表，其对应的折半查找判定树是一种特殊的二叉树结构。当 n=0 时，该树为空；而当 n>0 时：

- 根节点代表的是位于中间位置 mid=(n+1)/2 处的数据项。
- 左子树对应着前一半较小的部分 r[1]~r[mid−1] 构成的新有序列表所形成的折半查找判定树[^1]。
- 右子树则由较大一部分即 r[mid+1]~r[n] 组成新的有序序列建立起来的折半查找判定树。

这种结构使得每次比较都能排除掉大约一半数量级的可能性，从而大大提高了搜索效率，时间复杂度达到 O(log₂n)[^2]。

### 长度为 18 的顺序存储有序表的折半查找判定树构建过程

为了具体展示如何创建一棵针对含有 18 个元素的数组执行折半查找操作所需的判定树，下面给出 Python 编程语言中的实现方式：

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


def build_binary_search_tree(arr):
    if not arr:
        return None
    
    mid_index = (len(arr)) // 2
    root = TreeNode(arr[mid_index])
    
    # Recursively construct the left subtree with elements before mid.
    root.left = build_binary_search_tree(arr[:mid_index]) 
    
    # Recursively construct the right subtree with elements after mid.
    root.right = build_binary_search_tree(arr[mid_index + 1:]) 

    return root


# Example usage for an array of length 18.
sorted_array_example = list(range(1, 19))
bst_root_node = build_binary_search_tree(sorted_array_example)

上述代码片段定义了一个简单的 `TreeNode` 类来表示单个节点，并通过递归函数 `build_binary_search_tree()` 来按照给定规则构造整棵树。这里假设输入是一个已经排好序且不含重复值的列表 `arr`，其中包含了要被索引的所有数值。

### 平均查找长度计算

平均查找长度是指在一个特定大小 N 的集合上随机选取关键字 k 进行成功定位所需经过的关键字比较次数期望值 E(N)，可以利用以下公式近似估算:

\[E(N)=\sum_{i=1}^{N}\frac{D_i}{N}, \]

其中 \( D_i\) 表示第 i 层上的内部路径总长加上外部路径总长的一半。对于平衡良好的完全二叉树来说，在最坏情况下的最大深度接近 log₂N ，因此整体性能表现良好。