如何在偶索引升序、奇索引降序的数组中执行二分查找？

这个方法完全可行。原数组的偶索引元素本身是升序排列，奇索引元素是降序排列，各自都满足二分查找所需的有序性前提，所以可以分别对两类索引对应的元素子集执行二分查找，不会有问题。

具体实现思路 #

1. 偶索引子集处理：偶索引为0、2、4、6...，对应元素是升序序列，直接用标准的升序二分查找逻辑，只需将二分过程中的中间索引映射为实际数组的偶索引（即实际索引 = 2 * 二分mid值）。
2. 奇索引子集处理：奇索引为1、3、5、7...，对应元素是降序序列，需要调整二分的比较逻辑：当当前中间元素大于目标值时，目标值可能在右侧（因为降序）；当当前元素小于目标值时，目标值可能在左侧，同时中间索引映射为实际数组的奇索引（实际索引 = 2 * 二分mid值 + 1）。

代码示例（Python） #

def find_target(arr, target):
    # 查找偶索引的升序子集
    left, right = 0, len(arr) // 2
    while left <= right:
        mid = (left + right) // 2
        actual_idx = 2 * mid
        if actual_idx >= len(arr):
            right = mid - 1
            continue
        if arr[actual_idx] == target:
            return actual_idx
        elif arr[actual_idx] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    # 查找奇索引的降序子集
    left, right = 0, (len(arr)-1) // 2
    while left <= right:
        mid = (left + right) // 2
        actual_idx = 2 * mid + 1
        if actual_idx >= len(arr):
            right = mid - 1
            continue
        if arr[actual_idx] == target:
            return actual_idx
        elif arr[actual_idx] > target:
            # 降序中当前值比目标大，目标在右侧区域
            left = mid + 1
        else:
            # 当前值比目标小，目标在左侧区域
            right = mid - 1
    
    return -1

# 测试示例
arr = [-3,10,0,9,5,0,7,-1]
target = 5
result = find_target(arr, target)
print(f"目标值 {target} 的索引是: {result}")  # 输出4，符合预期

补充说明 #

• 时间复杂度：两次二分查找的时间复杂度都是O(log n)，整体仍为O(log n)，效率很高。
• 边界处理：代码中加入了actual_idx >= len(arr)的判断，避免当数组长度为奇数时，偶索引或奇索引的映射出现越界问题。

内容的提问来源于stack exchange，提问作者rana