Хоёртын хайлт(binary search) гэх алгоритмын тухай бичнэ. Энэ удаад энгийн нэг бодлого дээр ярилцъя.
Бодлого. Бидэнд өсөхөөр эрэмбэлэгдсэн N урттай дараалал байгаа гэж бодъё. Мөн Q ширхэг хүсэлт өгөгдөх ба хүсэлт бүрд нэг тоо байх ба энэ дараалалд тэр тоо байгаа эсэхэд хариулах юм. 1 <= N, Q <= 10^5, abs(a[i]) <= 10^9.
Анализ: Энгийн давталт ашиглан олж болно. Тэгвэл хугацаа хамгийн ихдээ Q*N болох юм. Энэ нь 10^10 ба маш их үйлдэл хийж байгаа юм. Тэгвэл хэрхэн хурдан шийдэх вэ? Анхаарах зүйл нь энэ дараалал өсөхөөр эрэмбэлэгдсэн байгаа. Бид одоо X гэсэн тоог энэ дараалалд байгаа эсэхийг олох гэж байгаа гэж бодъё. Тэгвэл энэ дарааллын голын элементийн утгыг бид 1 үйлдлээр мэдэж чадна. Энэ элементийг индекс нь mid=(n+1)/2 болох ба энд 3 салах юм.
- a[mid] == X бол бид шууд байгаа гэдгийг нь олж чадлаа.
- a[mid] > X бол (mid, mid+1,..., n) хүртэлх индекстэй бүр элемент нь бидний хайж байгаа тооноос эрс их нь тодорхой. Тэгвэл бид X тоог энэ бүгдтэй шалгах хэрэггүй ба хэрэв X тоо энэ дараалалд байдаг бол түүний индекс нь (1,2,...,mid) завсарт орших нь тодорхой юм.
- a[mid] < X бол (1, 2,..., mid) хүртэлх индекстэй бүх элемент нь бидний хайж байгаа тооноос эрс бага нь тодорхой юм. Тэгвэл бид X тоог энэ бүгдтэй шалгах хэрэггүй ба хэрэв X тоо энэ дараалалд байдаг бол түүний индекс нь (mid+1,mid+2,...,n) завсарт орших нь тодорхой юм.
Хэрэв 2, 3-р нөхцөл биелсэн тохиолдолд бид X тоог энэ дараалалд байгаа эсэхийг хараахан мэдэж чадаагүй юм. Хэрэв 2-р тохиолдолруу шилжсэн бол (1, mid-1) завсарт хайна. Эсрэг тохиолдолд (mid+1, N) завсарт хайх юм. Тэгвэл энэ бас л нэгэн дараалал ба бид өмнө хийсэн үйлдлээ дахин давтахад л хангалттай юм. Өөрөөр хэлбэл бид L(зүүн завсар), R(баруун завсар) гэсэн завсарт хайж байгаа бол mid = (L+R)/2 болох болно. Хэрэв нөхцөл 2 бол L = L, R = mid-1 болох юм. Харин 3 бол L=mid+1, R = R гэсэн завсарт хайх юм. Ингэснээр бидний 1 хүсэлтэд хариулах үйлдэл нь Log(N) болох ба нийтдээ Q*(logN)) болох юм. Доорх код энэ хаягдээр байгаа.
- //Хоёртын хайлт(Binary search)
- #include <bits/stdc++.h>
- using namespace std;
- int n, q, a[200000];
- bool BS( int X ) {
- // bool гэдэг төрөл нь зөвхөн 0 эсвэл 1 гэсэн утга л авдаг
- // Байгаа эсвэл байхгүй гэдгийг мэдэх ёстой тул 1 эсвэл 0
- // буцаахад хангалттай юм. TRUE = 1, FALSE = 0
- int L = 1, R = n;
- // Эхлээд бид 1-ээс n завсарт хайх юм.
- while( L <= R ) {
- // одоо хайх завсар оршин байх буюу зүүн зах нь баруун
- // захаасаа бага буюу тэнцүү тохиолдолд хайсаар байх болно.
- int mid = (L+R)/2; // энэ завсрын голын элементийн индекс
- if( a[mid] == X ) {
- // Нөхцөл 1 буюу энэ тоо байгаа тул бид 1-ыг буцаана.
- return true;
- }
- if( a[mid] > X ) {
- // Нөхцөл 2 буюу (mid, mid+1, ... , R) хүртэлх бүх тоо нь
- // X-ээс эрс их тул алгасах ба одоо бид L, mid-1 завсарт байгаа
- // эсэхийг шалгана.
- R = mid-1;
- } else {
- // Нөхцөл 3 буюу (L, L+1, ... , mid) хүртэлх бүх тоо нь
- // X-ээс эрс бага тул алгасах ба одоо бид mid+1, R завсарт байгаа
- // эсэхийг шалгана.
- L = mid+1;
- }
- }
- // хэрвээ бид хайж дуусаад ямар ч утга буцааж чадаагүй бол энэ тоо
- // энэ дараалалд байхгүй гэсэн үг ба 0 гэсэн утга буцаана.
- return false;
- }
- int main() {
- cin >> n >> q; // дарааллын урт болон хүсэлтийн тоог уншиж байна.
- for(int i = 1; i <= n; i++) {
- cin >> a[i]; // дарааллын элементүүдийг унших.
- }
- while( q-- ) { // q нь 0 ээс ялгаатай бол үргэлжилнэ гэсэн утгатай.
- // мөн q нэгээр хасагдана.
- int x; cin >> x; // бидний хариулах ёстой тоо.
- if( BS( x ) ) {
- // if( x ) гэсэн тохиолдолд x-ын утга нь 0 ээс ялгаатай бол үнэн
- // энэ тоо дараалалд байгаа гэсэн үг.
- cout << "YES" << endl;
- } else {
- // эсрэг тохиолдолд байхгүй гэсэн үг.
- cout << "NO" << endl;
- }
- }
- return 0;
- }
Comments
Post a Comment