建立一个线性表实现顺序查找和折半查找c++

建立一个线性表并实现在C++中实现顺序查找和折半查找需要先创建一个数组或动态存储结构来存储数据，并提供相应的函数来执行这两种搜索算法。

**顺序查找 (Sequential Search)**:
这种查找方法从列表的第一个元素开始，逐个比较每个元素，直到找到目标值或者遍历完整个列表。以下是简单的顺序查找实现：

template <typename T>
bool sequential_search(T* arr, int size, const T& target) {
    for (int i = 0; i < size; ++i) {
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}

在这个函数里，`arr` 是线性表的指针，`size` 是数组长度，`target` 是你要查找的目标值。如果找到就返回 `true`，否则返回 `false`。

**折半查找 (Binary Search)**:
适用于有序数组。这种方法通过不断将查找范围减半，提高查找效率。以下是二分查找的基本步骤的伪代码，实际在C++中可能会使用迭代或递归方式实现：

// 假设排序后的数组 arr 和其长度 size
bool binary_search(T* arr, int left, int right, const T& target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return true;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

这个函数接收左边界 `left`、右边界 `right`，以及目标值 `target`。每次比较中间元素，如果相等则返回，小于目标缩小左边界，大于目标扩大右边界，直到找到或范围为空。