用C语言设计一个递归算法，实现在一个线性表中搜索一个指定关键字值的元素

在C语言中，你可以使用递归算法来实现线性表（如数组）中的搜索功能。这里我们假设有一个简单的整数数组作为线性表。以下是一个基本的递归函数，用于在一个已排序的数组中查找特定的关键字值：

#include <stdio.h>

// 定义递归函数 search，参数为数组、数组长度、目标值和当前索引
int search(int arr[], int size, int target, int index) {
    // 基本情况：如果当前索引超过数组长度或目标值等于当前元素，返回该索引
    if (index >= size || arr[index] == target)
        return index;

    // 如果目标值小于当前元素，继续在左半部分递归搜索
    else if (arr[index] > target)
        return search(arr, size, target, index + 1); // +1表示向右移动

    // 否则，目标值大于当前元素，继续在右半部分递归搜索
    else
        return search(arr, size, target, index - 1); // -1表示向左移动
}

int main() {
    int arr[] = {1, 3, 5, 7, 9}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5; // 要查找的目标值

    int result = search(arr, size, target, 0);

    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found in the array.\n");

    return 0;
}