建立一个顺序表，输入一个关键字，对该表进行顺序查找和折半查找。

建立一个顺序表，可以使用数组或链表来实现。输入一个关键字后，可以通过顺序查找或折半查找来查找该关键字在表中的位置。

顺序查找是从表的第一个元素开始逐个比较，直到找到目标元素或者遍历完整个表。时间复杂度为O(n)。

折半查找是在有序表中进行查找，每次将查找区间缩小一半，直到找到目标元素或者区间为空。时间复杂度为O(log n)。

需要注意的是，顺序查找适用于表长度较小或者无序的情况，而折半查找适用于表长度较大且有序的情况。

相关问题

c++建立一个无序表并实现对其顺序查找和折半查找

C++可以使用STL中的unordered_map来建立一个无序表，也可以手动实现哈希表。

顺序查找可以使用for循环遍历整个表，找到目标元素即返回其位置。折半查找则需要先将表按照关键字排序，然后使用二分法查找目标元素。

以下是一个简单的示例代码：

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

// 手动实现哈希表
class MyHashMap {
private:
    vector<pair<int, int>> data;
public:
    MyHashMap() {}

    void put(int key, int value) {
        for (auto& p : data) {
            if (p.first == key) {
                p.second = value;
                return;
            }
        }
        data.emplace_back(key, value);
    }

    int get(int key) {
        for (auto& p : data) {
            if (p.first == key) {
                return p.second;
            }
        }
        return -1;
    }
};

int main() {
    // 使用STL中的unordered_map
    unordered_map<int, int> umap;
    umap[1] = 10;
    umap[2] = 20;
    umap[3] = 30;
    cout << umap[2] << endl; // 输出20

    // 手动实现哈希表
    MyHashMap mymap;
    mymap.put(1, 10);
    mymap.put(2, 20);
    mymap.put(3, 30);
    cout << mymap.get(2) << endl; // 输出20

    // 顺序查找
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int target = 5;
    for (int i = ; i < nums.size(); i++) {
        if (nums[i] == target) {
            cout << "顺序查找：找到了，位置为" << i << endl;
            break;
        }
    }

    // 折半查找
    sort(nums.begin(), nums.end());
    int left = , right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            cout << "折半查找：找到了，位置为" << mid << endl;
            break;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return ;
}

随机产生一组m到n之间的一组整数，根据这一组整数完成如下操作：\n\n建立一个顺序表，输入一个关键字，对该表进行顺序查找和折半查找。

### 回答1：
首先，我们需要随机产生一组m到n之间的一组整数。可以使用Python中的random库来实现：

import random

m = 1
n = 100
num_list = [random.randint(m, n) for i in range(10)]

这样就可以生成一个包含10个随机整数的列表num_list，其中每个整数都在1到100之间。

接下来，我们需要建立一个顺序表。可以使用Python中的列表来实现：

def create_seq_list(num_list):
seq_list = []
for num in num_list:
seq_list.append(num)
return seq_list

seq_list = create_seq_list(num_list)

现在我们已经有了一个顺序表seq_list，接下来可以输入一个关键字，对该表进行顺序查找和折半查找。

顺序查找可以使用Python中的for循环来实现：

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

key = 50
index = seq_search(seq_list, key)
if index != -1:
print("顺序查找：关键字{}在顺序表中的位置为{}".format(key, index))
else:
print("顺序查找：关键字{}不在顺序表中".format(key))

折半查找可以使用Python中的递归函数来实现：

def binary_search(seq_list, key, low, high):
if low > high:
return -1
mid = (low + high) // 2
if seq_list[mid] == key:
return mid
elif seq_list[mid] > key:
return binary_search(seq_list, key, low, mid-1)
else:
return binary_search(seq_list, key, mid+1, high)

key = 50
index = binary_search(seq_list, key, , len(seq_list)-1)
if index != -1:
print("折半查找：关键字{}在顺序表中的位置为{}".format(key, index))
else:
print("折半查找：关键字{}不在顺序表中".format(key))

### 回答2：
首先，我们需要随机产生一组m到n之间的一组整数。可以使用Python的random模块来实现。以下是产生10个1到100之间的随机整数的代码示例：

import random

m = 1
n = 100
num_list = []
for i in range(10):
    num_list.append(random.randint(m, n))

print(num_list)

接下来，我们需要建立一个顺序表。顺序表可以用Python中的列表来表示。我们可以直接将上面随机生成的num_list作为顺序表。以下是示例代码：

seq_list = num_list
print(seq_list)

现在，我们可以输入一个关键字，并对该表进行顺序查找和折半查找。以下是代码示例：

# 顺序查找
def sequential_search(seq_list, key):
    for i in range(len(seq_list)):
        if seq_list[i] == key:
            return i
    return -1

key = int(input("请输入关键字："))
pos = sequential_search(seq_list, key)
if pos != -1:
    print("在位置", pos)
else:
    print("未找到该关键字")

# 折半查找（二分查找）
def binary_search(seq_list, key):
    left = 0
    right = len(seq_list) - 1
    while left <= right:
        mid = (left + right) // 2
        if seq_list[mid] == key:
            return mid
        elif seq_list[mid] > key:
            right = mid - 1
        else:
            left = mid + 1
    return -1

key = int(input("请输入关键字："))
pos = binary_search(sorted(seq_list), key)
if pos != -1:
    print("在位置", pos)
else:
    print("未找到该关键字")

这样，我们就完成了对随机产生的一组m到n之间的一组整数，建立顺序表后进行顺序查找和折半查找的操作。

### 回答3：
首先，我们需要生成一个m到n之间的一组整数。可以使用Python中的random模块中的randrange函数实现。比如，生成10到50之间的10个整数，可以这样写：

import random

m = 10
n = 50
num_list = [random.randrange(m, n+1) for i in range(10)]
print(num_list)

接下来，我们需要建立一个顺序表。顺序表是一种简单的数据结构，可以用Python中的列表来实现。我们可以把上一步生成的num_list作为列表的元素，实现如下：

num_list = [18, 48, 21, 22, 45, 38, 29, 50, 17, 36]  # 假设生成的随机整数列表为这个
num_list.sort()  # 建立顺序表前先对列表元素排序，以保证顺序查找和折半查找的正确性

print(num_list)  # 打印列表

此时，num_list就是我们需要进行查找的顺序表。

接下来，我们可以进行顺序查找和折半查找。

顺序查找是一种简单的查找算法，可以在一个无序的列表中查找指定元素。实现这个算法是很简单的，只需要从列表的第一个元素开始，逐个对比元素，直到找到目标元素为止。如果找不到，就返回一个特定的值。

下面是实现顺序查找的代码：

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

这个函数接受两个参数，一个是列表lst，另一个是待查找的关键字key。它从列表的第一个元素开始逐个对比，如果找到了等于key的元素，就返回该元素在列表中的下标。如果没有找到，就返回-1。

我们可以测试一下这个函数：

idx = seq_search(num_list, 38)
if idx >= 0:
    print("顺序查找：找到了，下标为", idx)
else:
    print("顺序查找：没找到")

折半查找是一种更高效的查找算法，可以在一个有序的列表中查找指定元素。顾名思义，它是通过不断将查找区间缩小一半，来快速定位目标元素的位置的。

下面是实现折半查找的代码：

def bin_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:
            low = mid + 1
        else:
            high = mid - 1
    return -1

这个函数也接受两个参数，一个是列表lst，另一个是待查找的关键字key。函数中使用low和high两个变量来表示当前查找的区间范围，初始化时区间为整个列表。在每次循环中，计算区间的中间位置mid，如果mid处的元素等于key，则返回mid。如果mid处的元素小于key，则将low更新为mid+1，因为在mid左侧的元素都比key小，不用再考虑了。如果mid处的元素大于key，则将high更新为mid-1，因为在mid右侧的元素都比key大，不用再考虑了。如果循环完成后仍然没有找到key，则返回-1。

我们也可以测试一下这个函数：

idx = bin_search(num_list, 38)
if idx >= 0:
    print("折半查找：找到了，下标为", idx)
else:
    print("折半查找：没找到")

这样，我们就完成了顺序查找和折半查找的演示。需要注意的是，在实际使用中，可以使用Python中的内置函数来实现这些操作，比如lst.index(key)可以实现顺序查找，bisect.bisect_left(lst, key)可以实现折半查找。这些函数的效率要比自己实现的函数高得多，所以更推荐使用。