[이분탐색] 백준 1920 수찾기 C++

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

1920번: 수 찾기

---

---

풀이 : 

 기본적인 이분탐색 문제 풀이! STL라이브러리에 binary_search 함수가 정의 되어 있지만 이분탐색 문제를 많이 풀어보진 않아서 간단한 문제정도는 직접 함수를 구현해 보려한다.

while문 사용도 가능하지만 재귀함수 사용해서 풀어봄

기본적인 원리는 배열을 정렬한 후 mid 값을 이용해서 목표값을 찾는 방법이다! 가령 [1,2,3,4,5] 값을 가지는 배열에서 선형적으로 검색할 수 있지만 배열의 크기가 커지면 비효율 적이므로 내가 찾고 자 하는 target 값을 설정해서 target 값과 mid 값을 비교하면서 찾는 방법 !

 

target 값이 4 라면?

mid 값이 3으로 target값인 4가 크므로 end는 그대로 두고 start 부분을 mid +1 로 옮긴다.

index	0	1	2	3	4
arr	1	2	3	4	5
	start		mid		end

index	0	1	2	3	4
	1	2	3	4	5
				start, mid	end

배열의 길이가 더 길어져도 이런식으로 반복하다보면 mid 값과 일치하는 부분을 찾을 수 있고 혹시 배열 내에 target 값이 없다면 start = mid+1 또는 end = mid -1 을 하는 과정에서 start < end 되는 경우가 발생한다 이경우에 0을 출력해주면됨

단 주의 해야할 것은 이 문제 말고 다른 문제의 경우 mid 범위를 설정하는 과정에서 무한루프에 빠질 수 있기 때문에(만약 배열의 길이가 7이면 3 / 4 이런식으로 정확히 둘로 나눠 지지 않음) 이분탐색 문제를 풀때는 범위설정이 중요하다!

코드 : 

#include <iostream>
#include <algorithm>
#define endl '\n'
#define MAX 100005

using namespace std;
int nArr[MAX];
int n, m;

void binary_search(int start, int end, int target) {

	int mid = (start + end) / 2;
	if (start > end) {
		cout << "0" << endl;
		return;
	}
	else {
		if (nArr[mid] == target) {
			cout << "1" << endl;;
			return;
		}
		else {
			if (nArr[mid] < target) {
				binary_search(mid + 1, end, target);

			}
			else if (nArr[mid] > target) {
				binary_search(start, mid - 1, target);
			}
		}


	}


}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> nArr[i];
	}
	sort(nArr, nArr + n);
	cin >> m;
	int tmp;
	for (int i = 0; i < m; i++) {
		tmp = 0;
		cin >> tmp;
		binary_search(0, n - 1, tmp);
	}
}