已知一个有n个元素的从小到大排列的整数序列,序列中的数据没有重复。现在要查找一个给定的值key,输出key在此序列中出现的位置。 例如:在序列[1,2,3,5,8,9,12,21,37,49,55,613]中,查找5的结果是4,表示找到了,位

置是4（从0开始计数）。

这是一个经典的二分查找问题，可以使用二分查找算法来解决。具体思路如下：

1. 将序列的左右边界设为0和n-1。

2. 如果左边界大于右边界，则说明序列中没有找到key，返回-1。

3. 计算中间位置mid，如果序列中第mid个元素等于key，则返回mid；如果第mid个元素大于key，则在左半边继续查找；如果第mid个元素小于key，则在右半边继续查找。

代码实现如下：

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

使用示例：

nums = [1, 2, 3, 5, 8, 9, 12, 21, 37, 49, 55, 613]
key = 5
print(binary_search(nums, key))  # 输出4

注意：该算法的前提是序列已经有序，如果序列无序，则需要先进行排序才能使用二分查找算法。

相关问题

C语言：实验8-必选题（1） 二分查找（折半查找） 分数 50 作者 于延 单位 哈尔滨师范大学 描述 已知一个有n个元素的从小到大排列的整数序列，序列中的数据没有重复。现在要查找一个给定的值key，输出key在此序列中出现的位置。 例如：在序列[1,2,3,5,8,9,12,21,37,49,55,613]中,查找5的结果是4,表示找到了，位置是4（第4个数）. 输入 第一行包含一个正整数k，表示有k组测试数据。1 <= k <= 100。接下来是k组数据。 对于每组数据，首先包含一行两个整数，n和key,表示该组数据整数序列的元素个数n和要查找的值key。(1 <=n<=1000) 然后的一行中包含n个从小到大排列好的整数，依次给出序列的每个元素，相邻两个整数之间用空格隔开。 题目中所有元素和key的绝对值不超过10000。 输出 对于每组数据，若序列中存在key，输出key第一次出现的位置；否则输出-1。 每个输出单独占一行。

这道题目可以使用二分查找（折半查找）进行解答，代码如下：

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) {
            return mid + 1;
        } else if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int k;
    scanf("%d", &k);
    while (k--) {
        int n, key;
        scanf("%d %d", &n, &key);
        int arr[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        int pos = binarySearch(arr, n, key);
        printf("%d\n", pos);
    }
    return 0;
}

这里使用了二分查找（折半查找）算法进行查找，通过设置左右边界来不断缩小查找范围，直到查找到目标元素或者查找范围为空。最后输出目标元素的位置即可。

需要注意的是，题目中要求输出目标元素第一次出现的位置，因此不能直接使用库函数`bsearch`进行查找，而是需要自己实现二分查找算法。另外，由于题目保证了序列中的数据没有重复，因此找到目标元素后直接返回其位置即可。

使用c语言实现 二分查找（折半查找） 描述 已知一个有n个元素的从小到大排列的整数序列，序列中的数据没有重复。现在要查找一个给定的值key，输出key在此序列中出现的位置。 例如：在序列[1,2,3,5,8,9,12,21,37,49,55,613]中,查找5的结果是4,表示找到了，位置是4（第4个数）. 输入 第一行包含一个正整数k，表示有k组测试数据。1 <= k <= 100。接下来是k组数据。 对于每组数据，首先包含一行两个整数，n和key,表示该组数据整数序列的元素个数n和要查找的值key。(1 <=n<=1000) 然后的一行中包含n个从小到大排列好的整数，依次给出序列的每个元素，相邻两个整数之间用空格隔开。 题目中所有元素和key的绝对值不超过10000。 输出 对于每组数据，若序列中存在key，输出key第一次出现的位置；否则输出-1。 每个输出单独占一行。 样例输入 3 5 3 2 3 5 6 7 4 5 1 2 3 4 1 1 1 样例输出 2 -1 1

以下是用 C 语言实现的二分查找代码：

#include <stdio.h>

// 二分查找函数，a为从小到大排列的数组，n为数组长度，key为要查找的值
int binarySearch(int a[], int n, int key) {
    int left = 0; // 左边界
    int right = n - 1; // 右边界

    while (left <= right) {
        int mid = left + (right - left) / 2; // 中间位置
        if (a[mid] == key) {
            return mid; // 找到了，返回位置
        } else if (a[mid] < key) {
            left = mid + 1; // key在右半边，缩小范围
        } else {
            right = mid - 1; // key在左半边，缩小范围
        }
    }

    return -1; // 没有找到，返回-1
}

int main() {
    int k; // 测试数据组数
    scanf("%d", &k);

    while (k--) {
        int n, key; // 数组长度和要查找的值
        scanf("%d %d", &n, &key);

        int a[n]; // 数组
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }

        int pos = binarySearch(a, n, key); // 调用二分查找函数
        printf("%d\n", pos);
    }

    return 0;
}

输入格式：
第一行一个正整数k，表示有k组测试数据。
接下来是k行，每行包括两个整数n和key，表示该组数据整数序列的元素个数n和要查找的值key。
接下来的一行中包含n个从小到大排列好的整数，依次给出序列的每个元素，相邻两个整数之间用空格隔开。

输出格式：
对于每组数据，若序列中存在key，输出key第一次出现的位置；否则输出-1。
每个输出单独占一行。

时间复杂度：O(logn)