dalao帮忙看看,第一个wa,最后一个tle了(悲)

P2249 【深基13.例1】查找

chaydo123 @ 2023-04-02 15:11:57

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
int nums[MAXN];
int find(int x, int n) {
    int left = 1;
    int right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < x) 
            left = mid + 1;
        else if (nums[mid] > x)
            right = mid - 1;
        else {
            while (nums[mid] == x)  mid--;
            return mid + 1;
        }
    }
    return -1;
}
int main() {
    int n, m;
    int x;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> nums[i];
    }
    for (int i = 1; i <= m; i ++) {
        cin >> x;
        cout << find(x, n) << " ";
    }
    return 0;
} 

by chaydo123 @ 2023-04-02 15:29:56

while (nums[mid] == x && mid >= 1)  mid--;

我加了一个判断,第一个点也过了,剩下最后一个点超时了


by dama1978 @ 2023-06-30 09:29:28

寻找相同值时,还是一个一个找,就超时了

int obSearch(int q){ int left,right,mid; left=1; right=n; while(left<right){ mid=(left+right)/2; if(a[mid]>=q){ right=mid; }else{ left=mid+1; } } if(a[left]==q) return left; else return -1; }


|