二分查找（Binary Search）

# /*
# 二分查找（Binary Search）
# --------------------------------------------------------
# 原理：
# 针对“有序序列”进行高效查找。
# 通过不断取中间元素，与目标值比较，
# 决定下一步往左半区或右半区继续查找。
#
# 每次排除一半区间，因此效率极高。
# */

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

    # 在左右指针未交错时持续查找
    while left <= right:
        mid = (left + right) // 2
        mid_value = arr[mid]

        if mid_value == target:
            return mid       # 找到
        elif mid_value < target:
            left = mid + 1   # 去右半部分
        else:
            right = mid - 1  # 去左半部分

    return -1                # 未找到


# 示例演示（必须是有序列表）
data = [1, 3, 5, 7, 9, 11, 13]
print("数据：", data)

pos = binary_search(data, 7)
print("查找 7 的位置:", pos)

pos = binary_search(data, 10)
print("查找 10 的位置:", pos)

# --------------------------------------------------------
# 关键要点总结：
# 1) 仅适用于“有序序列”，无序数据必须先排序；
# 2) 每轮比较可排除一半区间，效率远高于顺序查找；
# 3) 时间复杂度 O(log n)，空间复杂度 O(1)；
# 4) 查找规模越大，优势越明显；
# 5) 常用于搜索类算法、性能要求高的场景。
# */

# 数据： [1, 3, 5, 7, 9, 11, 13]
# 查找 7 的位置: 3
# 查找 10 的位置: -1