Octave / MATLAB 第69题：递归函数算法：在有序向量中执行二分查找

题目

编写递归函数 <code>rec_binary_search(vec, target, low, high)</code>，在已按升序排列的整数向量中递归检索目标元素所在下标。若找到返回下标，若不存在返回 -1。

输入格式：无需外部输入。

输出格式：分别测试命中元素与未命中元素的查找结果。

数据范围与约定：递归二分查找。

思路与算法

1. 二分查找条件
数组必须严格有序。时间复杂度为 $O(\log N)$。

2. 递归出口
若 low > high 表示目标值不在搜索区间内，返回 -1。

3. 防溢中点计算
中点下标计算使用 floor((low + high) / 2)。

完整程序

% Octave / MATLAB 第69题：递归二分查找
1;

function idx = rec_binary_search(v, target, low, high)
    if low > high
        idx = -1; % 未找到
        return;
    end
    
    mid = floor((low + high) / 2);
    if v(mid) == target
        idx = mid;
    elseif v(mid) > target
        idx = rec_binary_search(v, target, low, mid - 1);
    else
        idx = rec_binary_search(v, target, mid + 1, high);
    end
end

% 主程序
arr = [11, 23, 35, 47, 52, 68, 74, 89, 95];

target1 = 52;
target2 = 99;

pos1 = rec_binary_search(arr, target1, 1, length(arr));
pos2 = rec_binary_search(arr, target2, 1, length(arr));

fprintf("有序序列: %s\n", mat2str(arr));
fprintf("检索目标 %d: 位于下标 %d\n", target1, pos1);
fprintf("检索目标 %d: 检索结果 %d (不存在)\n", target2, pos2);

运行示例

输出：

有序序列: [11 23 35 47 52 68 74 89 95]
检索目标 52: 位于下标 5
检索目标 99: 检索结果 -1 (不存在)