大佬看看代码,用得是二分法,案例可以通过,不知道是不是数据太大的原因

P2249 【深基13.例1】查找

qingmin123 @ 2023-03-14 15:03:30

#include<iostream>
#define N 1000001
#define M 100001
using namespace std;
int arr[N];
int brr[M];

int main()
{
    int n, m;
    int left, mid, right,k,flag=0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    for (int j = 0; j < m; j++)
    {
        cin >> brr[j];
    }

    for (k = 0; k < m; k++)
    {
        left = 0; right = n - 1; int h;//h是用来查找第一次出现 的循环变量
        while (left < right)
        {
            mid = (left + right) / 2;
            if (arr[mid] == brr[k])
            {
                for ( h = mid;; h--)
                {
                    if (arr[h] != arr[h - 1])
                    {
                        break;
                    }
                }
                cout << h + 1 << " ";
                break;
            }
            else if (brr[k] > arr[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }

        }
        if (left >= right)
        {
            cout << "-1" << " ";
        }

    }

    return 0;
}

by qingmin123 @ 2023-03-14 15:04:45

那个flag 忘记删了


by Ruiqun2009 @ 2023-03-14 16:07:29

@qingmin123 有两点缺陷:

  1. 未关闭流同步;
  2. 在全部是相同的数时会变成 O(n)

by qingmin123 @ 2023-03-14 20:43:34

@Ruiqun2009 感谢感谢


|