fork download
  1. //Хоёртын хайлт(Binary search)
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int n, q, a[200000];
  6.  
  7. bool BS( int X ) {
  8. // bool гэдэг төрөл нь зөвхөн 0 эсвэл 1 гэсэн утга л авдаг
  9. // Байгаа эсвэл байхгүй гэдгийг мэдэх ёстой тул 1 эсвэл 0
  10. // буцаахад хангалттай юм. TRUE = 1, FALSE = 0
  11. int L = 1, R = n;
  12. // Эхлээд бид 1-ээс n завсарт хайх юм.
  13.  
  14. while( L <= R ) {
  15. // одоо хайх завсар оршин байх буюу зүүн зах нь баруун
  16. // захаасаа бага буюу тэнцүү тохиолдолд хайсаар байх болно.
  17. int mid = (L+R)/2; // энэ завсрын голын элементийн индекс
  18.  
  19. if( a[mid] == X ) {
  20. // Нөхцөл 1 буюу энэ тоо байгаа тул бид 1-ыг буцаана.
  21. return true;
  22. }
  23.  
  24. if( a[mid] > X ) {
  25. // Нөхцөл 2 буюу (mid, mid+1, ... , R) хүртэлх бүх тоо нь
  26. // X-ээс эрс их тул алгасах ба одоо бид L, mid-1 завсарт байгаа
  27. // эсэхийг шалгана.
  28. R = mid-1;
  29. } else {
  30. // Нөхцөл 3 буюу (L, L+1, ... , mid) хүртэлх бүх тоо нь
  31. // X-ээс эрс бага тул алгасах ба одоо бид mid+1, R завсарт байгаа
  32. // эсэхийг шалгана.
  33. L = mid+1;
  34. }
  35. }
  36. // хэрвээ бид хайж дуусаад ямар ч утга буцааж чадаагүй бол энэ тоо
  37. // энэ дараалалд байхгүй гэсэн үг ба 0 гэсэн утга буцаана.
  38. return false;
  39. }
  40.  
  41. int main() {
  42. cin >> n >> q; // дарааллын урт болон хүсэлтийн тоог уншиж байна.
  43.  
  44. for(int i = 1; i <= n; i++) {
  45. cin >> a[i]; // дарааллын элементүүдийг унших.
  46. }
  47.  
  48. while( q-- ) { // q нь 0 ээс ялгаатай бол үргэлжилнэ гэсэн утгатай.
  49. // мөн q нэгээр хасагдана.
  50. int x; cin >> x; // бидний хариулах ёстой тоо.
  51.  
  52. if( BS( x ) ) {
  53. // if( x ) гэсэн тохиолдолд x-ын утга нь 0 ээс ялгаатай бол үнэн
  54. // энэ тоо дараалалд байгаа гэсэн үг.
  55. cout << "YES" << endl;
  56. } else {
  57. // эсрэг тохиолдолд байхгүй гэсэн үг.
  58. cout << "NO" << endl;
  59. }
  60. }
  61.  
  62. return 0;
  63. }
Success #stdin #stdout 0s 4260KB
stdin
10 10
1 2 4 5 6 7 11 23 24 200
1
2
3
4
5
6
7
8
9
200
stdout
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES