[已解决]二分查找

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

2024-12-15 13:59:27

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. // 比较函数，用于qsort
   
5. int compare(const void *a, const void *b) {
   
6.     return (*(int *)a - *(int *)b);
   
7. }
   
8. 
   
9. // 二分查找函数
   
10. int binarySearch(int arr[], int size, int target) {
    
11.     int left = 0, right = size - 1;
    
12.     while (left <= right) {
    
13.         int mid = left + (right - left) / 2;
    
14.         if (arr[mid] == target) {
    
15.             return mid + 1; // 返回位置，从1开始
    
16.         }
    
17.         if (arr[mid] < target) {
    
18.             left = mid + 1;
    
19.         } else {
    
20.             right = mid - 1;
    
21.         }
    
22.     }
    
23.     return 0; // 未找到
    
24. }
    
25. 
    
26. int main() {
    
27.     int n, m;
    
28. 
    
29.     // 读取直到文件结尾
    
30.     while (scanf("%d", &n) != EOF) {
    
31.         int arr[n];
    
32.         
    
33.         // 读取n个整数
    
34.         for (int i = 0; i < n; i++) {
    
35.             scanf("%d", &arr[i]);
    
36.         }
    
37.         
    
38.         // 使用qsort进行排序
    
39.         qsort(arr, n, sizeof(int), compare);
    
40.         
    
41.         // 打印排序后的数组
    
42.         for (int i = 0; i < n; i++) {
    
43.             printf("%d", arr[i]);
    
44.             if (i < n - 1) {
    
45.                 printf(" ");
    
46.             }
    
47.         }
    
48.         printf("\n");
    
49. 
    
50.         // 读取查询次数
    
51.         scanf("%d", &m);
    
52.         int query[m];
    
53.         
    
54.         // 读取待查找的整数
    
55.         for (int i = 0; i < m; i++) {
    
56.             scanf("%d", &query[i]);
    
57.         }
    
58.         
    
59.         // 查找每个整数并输出结果
    
60.         for (int i = 0; i < m; i++) {
    
61.             printf("%d", binarySearch(arr, n, query[i]));
    
62.             if (i < m - 1) {
    
63.                 printf(" ");
    
64.             }
    
65.         }
    
66.         printf("\n");
    
67.     }
    
68. 
    
69.     return 0;
    
70. }

复制代码

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

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

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

跳转到最佳答案楼层

FishC

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. // 比较函数，用于qsort
   
5. int compare(const void *a, const void *b) {
   
6.     return (*(int *)a - *(int *)b);
   
7. }
   
8. 
   
9. // 二分查找函数
   
10. int binarySearch(int arr[], int size, int target) {
    
11.     int left = 0, right = size - 1;
    
12.     while (left <= right) {
    
13.         int mid = left + (right - left) / 2;
    
14.         if (arr[mid] == target) {
    
15.             return mid + 1; // 返回位置，从1开始
    
16.         }
    
17.         if (arr[mid] < target) {
    
18.             left = mid + 1;
    
19.         } else {
    
20.             right = mid - 1;
    
21.         }
    
22.     }
    
23.     return 0; // 未找到
    
24. }
    
25. 
    
26. int main() {
    
27.     int n, m;
    
28. 
    
29.     // 读取直到文件结尾
    
30.     while (scanf("%d", &n) != EOF) {
    
31.         int arr[n];
    
32.         
    
33.         // 读取n个整数
    
34.         for (int i = 0; i < n; i++) {
    
35.             scanf("%d", &arr[i]);
    
36.         }
    
37.         
    
38.         // 使用qsort进行排序
    
39.         qsort(arr, n, sizeof(int), compare);
    
40.         
    
41.         // 打印排序后的数组
    
42.         for (int i = 0; i < n; i++) {
    
43.             printf("%d", arr[i]);
    
44.             if (i < n - 1) {
    
45.                 printf(" ");
    
46.             }
    
47.         }
    
48.         printf("\n");
    
49. 
    
50.         // 读取查询次数
    
51.         scanf("%d", &m);
    
52.         int query[m];
    
53.         
    
54.         // 读取待查找的整数
    
55.         for (int i = 0; i < m; i++) {
    
56.             scanf("%d", &query[i]);
    
57.         }
    
58.         
    
59.         // 查找每个整数并输出结果
    
60.         for (int i = 0; i < m; i++) {
    
61.             printf("%d", binarySearch(arr, n, query[i]));
    
62.             if (i < m - 1) {
    
63.                 printf(" ");
    
64.             }
    
65.         }
    
66.         printf("\n");
    
67.     }
    
68. 
    
69.     return 0;
    
70. }

复制代码

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

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

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