[백준] 1920번 수 찾기

Binary search 정복기 - 1

문제

이분 탐색

정렬되어 있는 배열에서 데이터를 찾을 때, 탐색범위를 줄여가면서 찾아가는 search 알고리즘이다.

문제 풀이

Binary search의 조건이 정렬되어있는 경우에 사용할 수 있는 search 알고리즘이므로, 입력을 받고 바로 정렬을 한 이후에 배열의 크기의 중간을 구한다. array[mid]가 X라는 정수보다 적으면 범위를 start < X < mid - 1; array[mid]가 X라는 정수보다 크면 범위를 mid + 1 < X < end; 이러한 방식으로 범위를 반으로 줄여나가다 보면 결국에는 X가 배열 안에 존재 하는지 확인 할 수 있다.

---

전체코드 자세히 보기

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100000];
bool binary_search(int B,int size)
{
	if (arr[0] > B || arr[size - 1] < B){
		return false;
	}
	int start = 0;
	int end = size - 1;
	int middle;
	while (start <= end){
		middle = (start + end) / 2;
		if (B == arr[middle]){
			return true;
		}
		if (B > arr[middle]){
			start = middle + 1;
		}
		else{
			end = middle - 1;
		}
	}
	return false;
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
	int N,A;
	cin >> N;
	for (int i = 0; i < N; i++){
		cin >> A;
		arr[i] = A;
	}
	int M,B;
	cin >> M;
	sort(arr, arr+N);

	for (int i = 0; i < M; i++)
	{
		cin >> B;
		cout << binary_search(B, N) << "\n";
	}
}

---

문제 결과

문제 출처 https://www.acmicpc.net/problem/1920