折半查找是一种效率较高的查找方法，请回答下列问题: 2. ①折半查找的存储结构是什么样的; ②用类C的语言给出折半查找的非递归算法，关键之处给出注释: ③用类C的语言给出折半查找的递归算法，关键之处给出注释

① 折半查找通常适用于已经排序的数组或列表。存储结构上，它假设输入是一个动态数组（如`int *array`），并且元素是按照升序排列的。每个元素都有一个索引，数组的最后一个元素有一个特殊的标记，比如`array[n - 1]`，以便于在查找时确定中间位置。

② 非递归的折半查找算法（二分搜索）如下：

int binarySearch(int* array, int target, int low, int high) {
    if (low > high) return -1; // 结束条件，目标不在数组内

    int mid = low + (high - low) / 2; // 计算中间索引
    if (array[mid] == target) return mid; // 直接返回目标值的索引
    else if (array[mid] < target) return binarySearch(array, target, mid + 1, high); // 如果目标大，缩小左半部分
    else return binarySearch(array, target, low, mid - 1); // 否则缩小右半部分
}

// 关键之处注释：
// `mid` 表示当前查找范围的中心，`low + (high - low) / 2`计算出中间位置
// 判断相等、小于或大于目标，然后相应地更新查找范围。

③ 对应的递归版本：

int recursiveBinarySearch(int* array, int target, int low, int high) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] == target) return mid;
        else if (array[mid] < target) {
            return recursiveBinarySearch(array, target, mid + 1, high);
        } else {
            return recursiveBinarySearch(array, target, low, mid - 1);
        }
    }
    return -1; // 当前范围内未找到目标，返回-1
}

// 关键之处注释：
// 递归版同样以`mid`作为划分点，递归调用自身处理较小的查找范围。