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

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
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

Hãy đọc nội quy trước khi bình luận.


  • 1
    kietjumper  đã bình luận lúc 27, Tháng 3, 2025, 15:42 
    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)

  • 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.


  • -4
    super_god  đã bình luận lúc 8, Tháng 10, 2024, 2:39

    hello ae


  • 6
    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


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

    bài này dùng linear search


  • 3
    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


    • 3
      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


  • -3
    DKN13  đã bình luận lúc 11, Tháng 1, 2024, 12:58

    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....


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

    k qua nhỉ