Хоёртын хайлт гэх алгоритм хаа сайгүй л явж байдагдаа. Энгийн мөртлөө хүчтэй санааг агуулж байдаг. Ер нь нэрнүүдэд их учир бий шүү. Жишээ бодлого дээр авж үзье.

Бодлого

Бидэнд өсөхөөр эрэмбэлэгдсэн N урттай дараалал, Q ширхэг хүсэлт өгөгдөх ба хүсэлт бүрд нэг тоо байх ба энэ дараалалд тэр тоо байгаа эсэхэд хариулах юм. 1 <= N, Q <= 10^5, abs(a[i]) <= 10^9.

Analysis

Хүсэлт бүрийн хувьд N ширхэг тоо бүртэйгээ тэнцүү эсэхийг шалгахад болно. Тэгвэл бид 1 хүсэлтэнд хамгийн муудаа N үйлдлээр хариулах ба нийтдээ Q*N буюу 10^10 үйлдэл хийхнээ. Ажиллаж дуусахыг нь хүлээвэл барахгүй ээ.

Тэгвэл хэрхэн хурдан шийдэх вэ? Анхаарах зүйл нь энэ дараалал өсөхөөр эрэмбэлэгдсэн байгаа. Бид одоо X гэсэн тоог тухайн дараалалд байгаа эсэхийг олох гэж байгаа гэж бодъё. Тэгвэл энэ дарааллын голын элементийн утгыг бид 1 үйлдлээр мэдэж чадна. Тухайн голын index-г mid гэвэл mid = (n+1)/2 байна. Энэдээс ажиглах зүйл нь

  1. a[mid] == X буюу голын элемэнт нь тэнцүү бол шууд байгаа гэдгийг мэдчихлээ.
  2. a[mid] > X буюу голын элемэнт нь X-с их бол [mid, mid+1,..., n] хүртэлх индекстэй бүр элемент нь бидний хайж байгаа тооноос эрс их нь тодорхой. Тэгвэл бид X тоог энэ бүгдтэй шалгах хэрэггүй ба хэрэв X тоо энэ дараалалд байдаг бол түүний индекс нь [1,2,...,mid] завсарт орших нь тодорхой юм.
  3. a[mid] < X бол [1, 2,..., mid] хүртэлх индекстэй бүх элемент нь бидний хайж байгаа тооноос эрс бага нь тодорхой. Тэгвэл бид X тоог энэ бүгдтэй шалгах хэрэггүй ба хэрэв X тоо энэ дараалалд байдаг бол түүний индекс нь [mid+1,mid+2,...,n] завсарт орших нь тодорхой юм.

Хэрэв 2, 3-р нөхцөл биелсэн тохиолдолд бид X тоог энэ дараалалд байгаа эсэхийг хараахан мэдэж чадаагүй хэвээрээ л байна. Гэхдээ бид тухайн санаагаа дахин ашиглаад хэрэв 2-р тохиолдолруу шилжсэн бол [1, mid-1] завсарт хайна. Эсрэг тохиолдолд [mid+1, N] завсарт хайх юм. Энэ мэтчилэн тухайн дарааллыг хоёрт хэсэг хуваасаар байгаад оллоо гэж үзэхэд хамгийн муудаа log(n) үйлдэл хийх ба нийт зарцуулах үйлдэл нь Q*log(N) боллоо.

#include <bits/stdc++.h> 
using namespace std;

	int n, q, a[200000];

bool BS( int X ) {
	int L = 1, R = n;
	// Эхлээд бид 1-ээс n завсарт хайх юм.

	while( L <= R ) {
		int mid = (L+R)/2; // энэ завсрын голын элементийн индекс
		
		if( a[mid] == X ) {
			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;
		}
	}
	return false;
}

int main() {
	cin >> n >> q;

	for(int i = 1; i <= n; i++) {
		cin >> a[i]; 
	}

	while( q-- ) { 	
		int x; cin >> x; 

		if( BS( x ) ) { 
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	return 0;
}