折半查找和二叉树查找

折半查找（Binary Search）和二叉树查找（Binary Tree Search）是两种常见的查找算法。

1. 折半查找是一种在有序数组中查找指定元素的算法。它的基本思想是将数组分成两部分，然后判断目标元素与中间元素的大小关系，进而确定目标元素在哪一部分中。如果目标元素等于中间元素，则查找成功；如果目标元素小于中间元素，则在前一部分中继续查找；如果目标元素大于中间元素，则在后一部分中继续查找。通过不断缩小查找范围，最终可以找到目标元素或确定目标元素不存在于数组中。

2. 二叉树查找是一种在二叉树中查找指定元素的算法。二叉树是一种特殊的树结构，每个节点最多有两个子节点。在二叉树查找中，首先比较目标元素与当前节点的值的大小关系，如果相等则查找成功；如果目标元素小于当前节点的值，则在左子树中继续查找；如果目标元素大于当前节点的值，则在右子树中继续查找。通过不断比较和移动，最终可以找到目标元素或确定目标元素不存在于二叉树中。

下面是两种查找算法的示例代码：

1. 折半查找：

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

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
print("Index of target element:", result) # 输出：2

2. 二叉树查找：

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

def binary_tree_search(root, target):
    if root is None or root.val == target:
        return root

    if root.val < target:
        return binary_tree_search(root.right, target)
    else:
        return binary_tree_search(root.left, target)

# 构建二叉树
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)

target = 4
result = binary_tree_search(root, target)
if result is not None:
    print("Target element found in binary tree")
else:
    print("Target element not found in binary tree")