이분탐색 (Binary Search)

이분탐색

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

• 시간복잡도 : O(log N)

유의사함

• 이분탐색은 오름차순 정렬이 이미 완료된 리스트에 대해서만 적용할 수 있다.
  => 정렬이 안된경우, 반드시 sort() 와 같은 함수로 정렬을 하고 이분탐색을 적용하자!

• 무한 루프에 빠지지 않도록 mid 값을 정해야한다.

  • "정렬 유형" 의 경우는 merge sort, quick sort 등을 알 필요가 없으므로 STL sort 함수를 가져다 쓰면 땡이였다. 그러나 이분탐색은 그렇지 않다!

  • binary_search( ), upper_bound( ), lower_bound( ) 라는 내장 함수들이 있지만 주어진 정렬된 배열에서 특정 원소를 찾거나, 삽입할 위치를 찾거나 하는 문제에서는 직접 구현을 하지 않고 그냥 STL 을 사용하는게 편한다.

  • But, 대표적으로 Parametic search 처럼 STL 이 도움이 안되고 직접 이분탐색을 수행해야 하는 경우가 있다. 그럴때는 논리적으로 엄청 큰 실수를 한게 아닌데도 불구하고 무한 루프에 빠지는 경우가 종종 있다!

이분탐색 구현

#include <bits/stdc++.h>
using namespace std;

int a[100005];
int n;

// 원하는 값을 배열에 존재하는지 여부를 0과 1로 리턴하는 이분탐색 함수
int binarysearch(int target) {
	int st = 0;
	int en = n - 1;
	while (st <= en) {
		int mid = (st + en) / 2; 
		if (a[mid] < target)  // 목표값이 현재 중앙점보다 오른쪽에 있는경우 
			st = mid + 1;
		else if (a[mid] > target) // 목표값이 현재 중앙점보다 왼쪽에 있는경우
			en = mid - 1;
		else                 // 목표값을 찾은 경우 (a[mid] == target 인 경우)
			return 1;
	}
	return 0; // 목표값을 찾지 못한경우
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	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';
	}
}

unique : 중복제거함수

• "정렬이 된" 배열에서만 중복 원소들을 제거하는 함수

맨앞 인덱스부터 시작해서 인덱스 i와 i+1 의 원소를 비교하고 중복된다면 제거하는 방식이다.

중복이 완료된 배열에는, 중복이 제거되고 남은 원소들을 앞쪽으로 땡겨주고 남아있는 빈 공간들에게는 쓰레기 값이 저장된다. 그리고 쓰레기값이 시작되는 구간의 인덱스 값을 리턴해준다.

=> 이때 불필요한 쓰레기값을 삭제시키도록 코드를 구현해줘야함!

uni.erase(unique(uni.begin(), uni.end()), uni.end());
=> 중복원소 제거 완료 이후에 uni 배열(벡터) 에 담긴 원소들을 삭제

lower_bound

찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾는함수

예제

arr 부터 끝까지 탐색하면서 6 이상의 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환하는 예제입니다. arr 배열에서 6은 0,1,2,…, 5번째 인덱스에서 처음으로 등장합니다.

lower_bound의 반환형은 Iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 됩니다.

=>벡터의 경우 아래와 같이 v.begin()을 빼 주면 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5

	return 0;
}