查找算法入门：从顺序查找到二分查找

def sequential_search(arr, target):
    """
    顺序查找算法实现
    :param arr: 待查找的数组
    :param target: 目标值
    :return: 目标值的索引，如果不存在则返回-1
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 测试示例
data = [5, 2, 8, 1, 9, 3]
target_value = 8
result = sequential_search(data, target_value)
print(f"目标值 {target_value} 的索引位置: {result}")

def binary_search(arr, target):
    """
    二分查找算法实现（迭代版本）
    :param arr: 已排序的数组
    :param target: 目标值
    :return: 目标值的索引，如果不存在则返回-1
    """
    low, high = 0, 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

# 测试示例
sorted_data = [1, 3, 5, 7, 9, 11, 13, 15]
target_value = 11
result = binary_search(sorted_data, target_value)
print(f"目标值 {target_value} 的索引位置: {result}")

def binary_search_recursive(arr, target, low, high):
    """
    二分查找算法实现（递归版本）
    """
    if low > high:
        return -1
    
    mid = (low + high) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

# 使用递归版本
result_recursive = binary_search_recursive(sorted_data, target_value, 0, len(sorted_data)-1)
print(f"递归版本查找结果: {result_recursive}")

# 使用位运算优化mid计算
mid = low + ((high - low) >> 1)

# 提前终止优化（针对特定场景）
def optimized_sequential_search(arr, target):
    # 在数组末尾添加哨兵元素，减少比较次数
    arr.append(target)
    i = 0
    while arr[i] != target:
        i += 1
    arr.pop()  # 移除哨兵
    return i if i < len(arr) else -1