数据结构折半查找的思维导图

折半查找的思维导图如下：

graph TD;
    A(开始)-->B(取中间值mid);
    B-->C{查找值与mid对比};
    C--查找值大于mid-->D(在mid右侧继续查找);
    C--查找值小于mid-->E(在mid左侧继续查找);
    C--查找值等于mid-->F(查找成功);
    D-->B;
    E-->B;
    F-->G(结束);

相关问题

数据结构折半查找算法

折半查找算法，也称为二分查找算法，是一种在有序数组中查找给定值的高效算法。

算法步骤如下：
1. 初始化左指针 low 为数组起始位置，右指针 high 为数组末尾位置。
2. 计算中间位置 mid = (low + high) / 2。
3. 比较数组中间元素与目标值的大小：
- 若中间元素等于目标值，则返回查找成功。
- 若中间元素大于目标值，则将 high 更新为 mid - 1，继续在左半部分查找。
- 若中间元素小于目标值，则将 low 更新为 mid + 1，继续在右半部分查找。
4. 重复步骤2和步骤3，直到 low 大于 high，表示查找失败。

折半查找算法的时间复杂度为 O(log n)，其中 n 是数组的长度。它是一种效率较高的查找算法，但要求待查找的数组必须是有序的。

数据结构折半查找练习

当然，我可以帮助你练习折半查找算法。折半查找也被称为二分查找，它是一种高效的查找算法，适用于有序数组。

首先，让我们来了解一下折半查找的步骤：

1. 确定要查找的目标值。
2. 初始化左边界(left)为数组的第一个元素的索引，右边界(right)为数组的最后一个元素的索引。
3. 计算中间元素的索引(mid)，可以使用公式 `mid = (left + right) // 2`。
4. 比较中间元素与目标值：
- 如果中间元素等于目标值，返回中间元素的索引。
- 如果中间元素大于目标值，将右边界更新为mid-1，重复步骤 3。
- 如果中间元素小于目标值，将左边界更新为mid+1，重复步骤 3。
5. 重复步骤 3 和步骤 4，直到找到目标值或者左边界大于右边界。

下面是一个示例代码实现折半查找：

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 目标值不存在

# 示例用法
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
    print(f"目标值 {target} 在数组中的索引为 {result}")
else:
    print("目标值不存在于数组中")

你可以尝试使用不同的有序数组和目标值测试该算法。如果有任何问题，请随时向我提问。