백준 1920 : 수 찾기 (C++, 이분탐색)

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

이분탐색을 공부하기 위해 가장 기본이 되는 예제를 풀었다.

 

이분탐색 
left, right, mid 값으로 탐색 mid = (left + right)/2

 

이분 탐색 수행 방법
1. 배열을 이미 정렬해야 함 (여기서는 오름차순으로 언급할 예정)
2. left, right로 미드값 설정 mid = (left + right)/2
3. mid값과 구하고자 하는 값(A)을 비교해
3-1) 구하고자 하는 값이 mid보다 큰 경우(A>mid) : left = mid + 1;
3-2) 구하고자 하는 값이 mid보다 작은 경우(A<mid) right = mid -1;
위 과정을 left>right 가 될 때까지 반복, 구하고자 하는 값을 구할 때 까지 반복

이분탐색은 탐색 시간이 한 루프랑 반씩 줄어드므로 O(log(n))

 

아래 블로그에서 내용을 이해하고 작성하였다.

https://wootool.tistory.com/62

[알고리즘] 이분 탐색

<정답 작성 코드>

#include <iostream>
#include <algorithm>

using namespace std;
int A[100001];
int N, M;
int num, left ,right, mid;

int main() {

	// cin, cout 속도 줄이기 위한 코드 - 해당 문제는 시간초과나는 경우 빈번
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	//N과 배열A 입력 받기
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	//배열A 정렬하기 (오름차순)
	sort(A, A + N);

	//M입력받기
	cin >> M;

	//찾을 수 M번 입력 받기
	for (int i = 0; i < M; i++) {
		cin >> num;
		bool is_success = false;
		int left = 0, right = N-1;
		int mid;
		//left가 right보다 커지지 않을 때까지 반복. 즉, 이분탐색이 끝날 때까지 반복
		while (left <= right) {
			//mid값 설정
			mid = (left + right) / 2;

			// A[mid] 값이 찾는 수와 같을 경우 - 성공 표시
			if (A[mid] == num) {
				is_success = true;
				break;
			}
			// A[mid] 값이 찾는 수보다 클 경우 - right 재정의
			else if  (num < A[mid]) {
				right = mid - 1;
			}
			// A[mid] 값이 찾는 수보다 작을 경우 - left 재정의
			else {
				left = mid + 1;
			}
		}
		cout << is_success << "\n";
	}
	return 0;
}

 

처음에는 A[mid]와 num의 비교가 아닌, 멍청하게도 mid와 num비교로 답을 구하고 있어서 계속 틀렸다. 이거 못 찾았으면 열받아서 잠 못 잘 뻔...

근데 더 화나는 건 자꾸 시간 초과나서 자꾸 틀렸다... 나 말고도 이 문제에서 시간초과 나는 사람이 많았는데 대부분

endl -> "\n" 변경

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 추가

로 해결한 듯 하다. 

문제 한번 더럽게 까다롭네...