이분탐색
-
정렬되어 있는 배열에서 특정 데이터를 찾기위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위의 절반으로 줄여가며 찾는 탐색 방법
-
시간복잡도 : 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;
}