250924 - binary search

이것도 과제이긴 하지만, 너무 쉬우니까 그냥 공개로 해놨다.

 

#include <iostream>
#include <vector>

int binary_search(std::vector<int>& L, int start, int end, int tar) {
	if (start > end) return -1;
	int mid = (start + end) / 2;

	if (L[mid] == tar) return mid;
	else if (L[mid] < tar) return binary_search(L, mid + 1, end, tar);
	else if (L[mid] > tar) return binary_search(L, start, mid - 1, tar);
}

int main() {
	int t;
	std::cin >> t;

	for (int i = 0; i < t; i++) {
		int l, q;
		std::cin >> l;
		std::cin >> q;
		std::vector<int> L(l);
		std::vector<int> Q(q);
		std::vector<int> res(q);
		for (int j = 0; j < l; j++) {
			std::cin >> L[j];
		}
		for (int k = 0; k < q; k++) {
			std::cin >> Q[k];
			std::cout << binary_search(L, 0, l-1, Q[k]) << " ";
		}
		std::cout << "\n";
	}


	return 0;
}

 

처음에 시간 초과가 떴다..

뭐가 문젠가 했더니 재귀 호출 할 떄 마다 벡터 L 을 새로 복사해야 하는데,

이러면 하나의 값을 찾기 위해 어마어마한 복사 연산이 발생하기 때문에 시간 복잡도가 날 수 밖에 없다고 한다

 

그래서 원본 벡터의 주소만 넘겨주는 참조! 방식을 사용해 & 을 붙여줘서 해결했다

전체를 다 전달할 생각을 하지 말고 앞 뒤 인덱스만 넘기면 간단해진다

 

+ 입출력 속도 향상

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);

 

계속 까먹는다 까먹지 말자고