[已解决]二分查找

yangzhixiaohuli

对于输入的n个整数，先进行升序排序，然后进行二分查找。

输入格式:
测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n(1≤n≤100)，第二行输入n个各不相同的待排序的整数，第三行是查询次数m（1≤m≤100），第四行输入m个待查找的整数。

输出格式:
对于每组测试，分2行输出，第一行是排序后的升序的结果，每两个数据之间留一个空格；第二行是查找的结果，若找到则输出排序后元素的位置（从1开始，每两个数据之间留一个空格），否则输出0。

输入样例:
9
4 7 2 1 8 5 9 3 6
5
10 9 8 7 -1
输出样例:
1 2 3 4 5 6 7 8 9
0 9 8 7 0

这题用C语言或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

6 天前

要解决这个问题，我们需要执行几个步骤：首先对输入数组进行排序，然后实现二分查找来定位我们所需要查找的元素的位置。以下是一个简要的C语言代码示例，可以实现这个功能。

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 二分查找函数
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid + 1; // 返回位置，从1开始
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return 0; // 未找到
}

int main() {
    int n, m;

    // 读取直到文件结尾
    while (scanf("%d", &n) != EOF) {
        int arr[n];
        
        // 读取n个整数
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        
        // 使用qsort进行排序
        qsort(arr, n, sizeof(int), compare);
        
        // 打印排序后的数组
        for (int i = 0; i < n; i++) {
            printf("%d", arr[i]);
            if (i < n - 1) {
                printf(" ");
            }
        }
        printf("\n");

        // 读取查询次数
        scanf("%d", &m);
        int query[m];
        
        // 读取待查找的整数
        for (int i = 0; i < m; i++) {
            scanf("%d", &query[i]);
        }
        
        // 查找每个整数并输出结果
        for (int i = 0; i < m; i++) {
            printf("%d", binarySearch(arr, n, query[i]));
            if (i < m - 1) {
                printf(" ");
            }
        }
        printf("\n");
    }

    return 0;
}

### 代码说明：
1. **排序部分** 使用了 `qsort()` 函数，这是C标准库提供的一个快速排序函数。
2. **二分查找部分** 实现了一个基本的二分查找算法，返回找到的索引值加1（因为题目要求从1开始计数），如果没找到，则返回0。
3. **主函数** 持续读取输入直到文件结束，并按题目要求输出结果。

通过这种结构，你可以很好地实现题目要求的功能，并且代码清晰易于理解。如果有需要进一步的优化或调整，可以根据实际需要进行修改。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

要解决这个问题，我们需要执行几个步骤：首先对输入数组进行排序，然后实现二分查找来定位我们所需要查找的元素的位置。以下是一个简要的C语言代码示例，可以实现这个功能。

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 二分查找函数
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid + 1; // 返回位置，从1开始
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return 0; // 未找到
}

int main() {
    int n, m;

    // 读取直到文件结尾
    while (scanf("%d", &n) != EOF) {
        int arr[n];
        
        // 读取n个整数
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        
        // 使用qsort进行排序
        qsort(arr, n, sizeof(int), compare);
        
        // 打印排序后的数组
        for (int i = 0; i < n; i++) {
            printf("%d", arr[i]);
            if (i < n - 1) {
                printf(" ");
            }
        }
        printf("\n");

        // 读取查询次数
        scanf("%d", &m);
        int query[m];
        
        // 读取待查找的整数
        for (int i = 0; i < m; i++) {
            scanf("%d", &query[i]);
        }
        
        // 查找每个整数并输出结果
        for (int i = 0; i < m; i++) {
            printf("%d", binarySearch(arr, n, query[i]));
            if (i < m - 1) {
                printf(" ");
            }
        }
        printf("\n");
    }

    return 0;
}

### 代码说明：
1. **排序部分** 使用了 `qsort()` 函数，这是C标准库提供的一个快速排序函数。
2. **二分查找部分** 实现了一个基本的二分查找算法，返回找到的索引值加1（因为题目要求从1开始计数），如果没找到，则返回0。
3. **主函数** 持续读取输入直到文件结束，并按题目要求输出结果。

通过这种结构，你可以很好地实现题目要求的功能，并且代码清晰易于理解。如果有需要进一步的优化或调整，可以根据实际需要进行修改。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。