• 이분 탐색 = 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

이분 탐색 정렬

• 리스트에서 19 찾기

1. start, mid, end 로 리스트를 나눔

1. mid 이하에 19가 없으므로 범위를 반으로 줄일 수 있다.

1. 2의 과정 반복

1. 2의 과정 반복

1. O(logN) 시간 복잡도를 가짐

/* binary search */
#include <iostream>

int a[100005];
int n;

int bainarysearch(int target){
	int start = 0;
	int end = n-1;
	while(start <= end){
		int mid = (start + end) / 2;
		if(a[mid] < target)
			start = mid + 1;
		else if(a[mid] > target)
			end = mid - 1;
		else 
			return 1;
	}
	/* start > end 경우 while 문 탈출 */
	return 0;
}

/* lower_idx  = lower_bound(stl 함수) */
/* (반대) upper_bound(stl 함수) */
int lower_idx(int target, int len){
	int start = 0;
	int end = len;
	while(start < end){
		int mid = (start + end) / 2;
		if(a[mid] >= target) end = mid;
		else strat = mid + 1;
	}
return start;
}

int main(void){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n); /* 배열 정렬 */
	int m;
	cin >> m;
	while(m--){
		int t;
		cin >> t;
		cout << binarysearch(t) << '\\n';
	}
}

• STL에 binary_search 함수가 있기에 파라미터 안의 원소가 들어있는지 여부를 O(lg N)에 true 혹은 false 출력 된다.
  • binary_search(a, a+n, t)
    • a : start, a + n : end 지점, t : 찾을 원소

이분 탐색 주의 사항

1. 이분 탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 함
2. 무한 루프에 빠지지 않게 mid 값을 정해야 한다. (적절한 mid 값 정해야 함)