实现查找表的顺序查找与折半查找

顺序查找是一种简单直接的查找方法，从表的一端开始逐一比较关键字，直到找到或搜索完整个表为止。时间复杂度为O(n)。

折半查找是一种比较高效的查找方法，要求表中的数据元素必须是有序的。它的查找过程是将待查找的关键字与表中间位置的关键字比较，如果相等则查找成功，否则根据大小关系缩小查找范围，直到找到或查找区间为空为止。时间复杂度为O(logn)。

以下是两种查找方法的Python代码实现：

顺序查找：

def sequential_search(lst, key):
    for i in range(len(lst)):
        if lst[i] == key:
            return i
    return -1

折半查找：

def binary_search(lst, key):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == key:
            return mid
        elif lst[mid] > key:
            high = mid - 1
        else:
            low = mid + 1
    return -1

相关问题

c++实现查找表的顺序查找与折半查找

顺序查找的C++代码实现：

int sequential_search(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

折半查找的C++代码实现：

int binary_search(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

其中，`arr`是待查找的数组，`n`是数组的长度，`key`是要查找的关键字。顺序查找的时间复杂度为O(n)，折半查找的时间复杂度为O(logn)。

编写具体函数实现查找表的顺序查找与折半查找

顺序查找函数实现：

def sequential_search(arr, target):
    """
    顺序查找
    :param arr: 待查找的数组
    :param target: 目标值
    :return: 目标值在数组中的下标，若不存在则返回-1
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

折半查找函数实现：

def binary_search(arr, target):
    """
    折半查找
    :param arr: 待查找的数组（已有序）
    :param target: 目标值
    :return: 目标值在数组中的下标，若不存在则返回-1
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1

以上是 Python 语言的实现，其他编程语言的实现也是类似的。