summer_529 2023-06-10 17:36 采纳率: 84.6%
浏览 93
已结题

C++ 二分查找,数组找数

C++ 二分查找,数组找数,无法AC,修改后依然无法AC,请指教,悬赏,求AC代码~
【题目描述】
给定一个已经从小到大排好序的数组,数组内有n个元素。现在,你需要在数组中查找元素x,如果x存在,输出它在数组中的位置(如果数组中有多个x,输出位置最小的一个),如果不存在,输出“no”。
【输入格式】
输入包括多行:
第一行包含一个整数n(1<=n<107);
第二行输入n个整数(每个数不会超过107);
第三行输入一个整数k(1<=k<=1000),表示需要进行k次查找;
接下来输入k行,每行输入一个整数x(每个数不会超过107)
【输出格式】
输出k行,对应每次查找的结果。
【输入样例】
6
1 2 2 2 3 4
3
2
5
3
【输出样例】
2
no
5

  • 写回答

7条回答

  • 语言-逆行者 2023-06-10 18:59
    关注

    基于new bing修改后的编写:

    #include <iostream>
    using namespace std;
    
    int binary_search(int arr[], int len, int target) {
        int left = 0, right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) { // 找到目标数了
                while (mid > 0 && arr[mid - 1] == target) {//mid-1位置也是目标数,则在左半部分继续找
                    mid--;
                }
                return mid+1;
            } else if (arr[mid] < target) { // 目标数在右半部分
                left = mid + 1;
            } else { // 目标数在左半部分
                right = mid - 1;
            }
        }
        return -1; // 没有找到目标数
    }
    
    int main() {
        int n;
        cin >> n;
        int arr[n];
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int k;
        cin >> k;
        int result[k];
        for (int i = 0; i < k; i++) {
            int x;
            cin >> x;
            result[i] = binary_search(arr, n, x);
        }
        for (int i = 0; i < k; i++) {
            if (result[i] == -1) {
                cout << "no\n";
            } else {
                cout << result[i] << endl;
            }
        }
        return 0;
    }
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(6条)

报告相同问题?

问题事件

  • 系统已结题 6月18日
  • 已采纳回答 6月10日
  • 创建了问题 6月10日

悬赏问题

  • ¥15 (标签-STM32|关键词-智能小车)
  • ¥20 关于#stm32#的问题,请各位专家解答!
  • ¥15 (标签-python)
  • ¥15 第一个已完成,求第二个做法
  • ¥20 搭建awx,试了很多版本都有错
  • ¥15 java corba的客户端该如何指定使用本地某个固定IP去连接服务端?
  • ¥15 activiti工作流问题,求解答
  • ¥15 有人写过RPA后台管理系统么?
  • ¥15 Bioage计算生物学年龄
  • ¥20 如何将FPGA Alveo U50恢复原来出厂设置哇?