Tìm kiếm trong mảng - LCOJ: Luyện Code Online Judge

VT04 - Tìm kiếm trong mảng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho mảng số nguyên ~A~ có ~n~ phần tử, hãy tìm kiếm xem trong mảng có xuất hiện phần tử ~x~ hay không?

Input

Dòng 1 là số nguyên dương ~n~ (số lượng phần tử của mảngm ~n \le 10^6~) và số nguyên ~x~ (~|x| \le 10^9~) là giá trị cần tìm
Dòng tiếp theo là ~n~ số nguyên là các phần tử của mảng (~|a_{ij}| \le 10^9~)

Output

Nếu ~x~ xuất hiện ít nhất 1 lần trong mảng, in ra YES
Nếu ~x~ không có trong mảng, in ra NO

Sample

Input #1

5 3
1 2 3 4 5

Output #1

YES

Bình luận

Please read the guidelines before commenting.

FULL AC CHO AE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x, a;
    cin >> n >> x;
    while (n--)
    {
        cin >> a;
        if (a == x)
        {
            cout << "YES";
            return 0;
            break;
        }
    }
    cout << "NO";
    return 0;
}

-1

thanhtamvtr đã bình luận lúc 5, Tháng 12, 2025, 13:36

include <bits/stdc++.h>

using namespace std; long long a[1000000],n,x,i,ok; int main() { cin>>n>>x; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n;i++) if(a[i]==x){ok=a[i]; break;} if(ok==x)cout<<"YES"; else cout<<"NO"; return 0; } chép vào nè!

0

Tobaochau234 đã bình luận lúc 5, Tháng 12, 2025, 10:29 ← sửa 2 →

HELLO

-2

phanhongkien_2015 đã bình luận lúc 25, Tháng 10, 2025, 4:34

cs kho ko

0

Lam67 đã bình luận lúc 2, Tháng 10, 2025, 7:29

kho ghe

0

minhat đã bình luận lúc 18, Tháng 9, 2025, 8:39

Chặt chi nếu dùng C++ thì có thể xài multiset, hoặc xài duyệt mảng theo cách bth, vector hàm count....

-2

taphoccode đã bình luận lúc 4, Tháng 8, 2025, 16:04

bài ni python sài lặp for bth nha tại n tới 10^6 th nên sài for cho dễ hiểu

Các cách làm (cơ bản):
+ Dùng linear search (Duyệt mảng)
+ Dùng binary search (tìm kiếm nhị phân)
+ Dùng hàm count (nếu count(a, a + n, x) > 0 thì x có trong mảng a và ngược lại)

Code mẫu cho thuật toán tìm kiếm nhị phân(Binary Search):

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define io cin.tie(0)->ios_base::sync_with_stdio(0)
#define endl '\n'
#define pb push_back
#define fin for (int i = 1; i <= n; i++)
#define fjm for (int j = 1; j <= m; j++)
#define fis for (int i = 0; i < (int)s.size(); i++)
#define yes cout << "YES"
#define no cout << "NO"
#define fi first
#define se second
#define NAME ""
const int N = 1e6+2;
using namespace std;

ll a[N],n,x;

void solve()
{
    cin>>n>>x;
    fin cin>>a[i];
    sort(a+1, a+n+1);
    int l=1;
    int r=n;
    int mid;
    bool kt=false;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]< x) l=mid+1;
        else if (a[mid]>x) r=mid-1;
        else {kt=true;break;}
    }
    if(kt) yes;
    else no;
}

int main()
{
    io;
    if(fopen(NAME".inp","r"))
    {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
    solve();
}

1

chu_manh_thang_cpp đã bình luận lúc 6, Tháng 3, 2025, 11:51

ua cai code truoc cua tui sao lai bi tle vay

1

5kym4rk đã bình luận lúc 13, Tháng 3, 2025, 14:01

Cho mình xem với. Mình muốn xem lỗi.

11

hientm0978 đã bình luận lúc 12, Tháng 7, 2024, 3:53

nghĩ đơn giản thôi mấy ông ơi, không cần chặt cần vector gì đâu

6

Konomi đã bình luận lúc 15, Tháng 5, 2024, 17:09

bài này dùng linear search

2

thh đã bình luận lúc 21, Tháng 1, 2024, 3:58

Bài này dùng gì cx được vì n cùng lắm cx chỉ có 10^6 nên có thể vẫn ac đc nhưng nên tìm 1 số cách nhanh hơn chứ duyệt trâu thì lâu lắm

Vector thì chậm hơn mảng thường khoảng 2 - 3 lần đấy bạn

Bài này thì xài chặt nhị phân có thể là nhanh nhất rồi vì ~log_2(10^6)~ khoảng 20 thôi nên nếu n = ~10^9*10^3~ thì cx có gần 40 và bài này cũng sort được chỉ mất ~log_2(n)~ thôi nên cách này ok nha

1

sang41dz đã bình luận lúc 3, Tháng 2, 2024, 14:09

sort chi nlog(n) duoc thoi chu log(2,n) kieu chi vay ban

-2

letienlinh2005 đã bình luận lúc 4, Tháng 11, 2023, 16:15

k qua nhỉ