Binary Search

이진탐색

이진탐색 연습

1. 이진탐색의 기본

무조건 정렬이 되어 있어야 한다! 뀨

이진탐색 연습

[문제]

개빨라!

#include <iostream>

using namespace std;

int arr[8] = { -6,1,2,5,6,7,9,15 };
int bs(int start, int end) {

	while (start <= end) {
		int mid = (start + end) / 2;
		if (arr[mid] == 6)return 1;
		if (arr[mid] > 6)end = mid - 1;
		else { start = mid + 1; }
	}
	return 0;
}
int main() {

	int ret = bs(0, 7);
	if (ret == 1)cout << "o";

	return 0;
}

[출력]
o

실제로 바이너리서치 , 함수로 빼는경우 많기때문에 일케연습뀨뀨

바이너리서치트리 쓰는 이유

일케 자주 물어보는 형태,,,

for문으로하면 넘 느림,,,

바이너리서치트리로 찾으면 겁나빠름,,

쿼리 문제 많이,,

탐색방법

#include <iostream>
#include <string>

using namespace std;

string caroil = "###_______";


int maxN = 0;
int main() {
	int start = 0;
	int end = 9;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (caroil[maxN] == '#'&&maxN>mid) {
			break;
		}
		if (caroil[mid] =='#') {
			start = mid + 1;
		}
		else {
			end = mid - 1;
			maxN = mid;
		}
		
	}
	cout << maxN << "\n";


	return 0;
}

#include <iostream>
#include <string>

using namespace std;

string caroil = "######____";


int maxN = 0;
int main() {
	int start = 0;
	int end = 9;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (caroil[maxN] == '#'&&maxN>mid) {
			break;
		}
		if (caroil[mid] =='#') {
			start = mid + 1;

		}
		else {
			end = mid - 1;
			maxN = mid;
		}
		
	}
	cout << maxN << "\n";


	return 0;
}

내가한게 맞긴한데,,너무 헷갈린당

우선순위 큐

heap

push

값을 맨 마지막에 넣은다음 자신의 자리인지 확인한다.

top

pop

높이만큼 시간이 걸린다.
logN

Heap sort

오름차순 우선순위 큐

내림차순 우선순위 큐

1. 오름차순 우선순위 큐
   priority_queue<int, vector, greater>mq;
   밑에꺼랑 같당 기본형

priority_queuepq;

2. 내림차순 우선순위 큐

priority_queue<int, vector, less>mq;

민힙, 맥스힙 사용해보기

 #include <iostream>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int>>pq;

priority_queue<int, vector<int>, less<int>>mq;

int main() {

	pq.push(1);
	pq.push(3);
	pq.push(5);
	pq.push(7);

	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}

	mq.push(1);
	mq.push(3);
	mq.push(5);
	mq.push(7);

	while (!mq.empty()) {
		cout << mq.top() << " ";
		mq.pop();
	}

	return 0;
}