6.1 배열 이진탐색
배열 이진 탐색
- 이진 탐색의 필수 조건은 정렬!
- 탐색 범위가 유효해야함. (배열의 시작과 끝을 포함해야한다는 뜻)
- 오른쪽 탐색 구간이 left보다 크거나 같아야 함.
- mid = left + (right - left) / 2;
- 배열 a의 key 값 == a[mid] 이면 return mid;
else if (a[mid] > key) right = mid - 1;
else if(a[mid] < key) left = mid + 1;
기본적으로 index를 이용해서 배열 내 값을 탐색한다.
6.2 lower_bound()
- 정렬된 배열 a에서 a[i] >= key 인 조건을 만족하는 최소 인덱스 i를 돌려줌.
- 크기 N일 때 O(logN)의 시간 복잡도를 가짐.
- 추가적으로 key 존재x, key 값 이상의 범위 최솟값
- key 값 여러 개 존재 시 key 값이 처음으로 나오는 index 값을 되돌려줌.
C++ 표준 라이브러리에 존재하니 알아놓으면 유용할듯 싶다.
6.3 일반화한 이진 탐색법
이 부분이 이진 탐색에 대한 견해가 아예 바뀐 부분이다. 기존에는 그냥 마구잡이로 반틈씩 줄여나가서 최종 goal 값에 대한 확신이 없었다면 이제는 논리적으로 생각을 할 수 있게 됐다.
일반화한 이진 탐색법
각 정수 x에 대해 true/false로 판정하는 조건 P가 주어졌을 때 어떤 정수 l,r (l < r)이 존재하고 다음이 성립한다고 하자.
- P(l) = false
- P(r) = true
- 어떤 정수 M ( ㅣ < M <= r )이 존재하고 x < M인 x에 대해 P(x) = false이고, x>=M인 x에 대해 P(x) = true이다.
- 이때 D = r - 1이라면, 이진 탐색법은 M을 O(logD) 복잡도로 구할 수 있는 알고리즘이라고 한다.
구체적인 예로 mid = (left + right) / 2 일 때,
- P(mid) = true이면 right <- mid이고
- P(mid) = false이면 left <- mid 로 갱신되는 것이다.
이렇게 갱신해 나가다보면 결국 right는 P(right) = true를 만족하는 최소 정수
P(left) = false를 만족하는 최대 정수가 되는 것이다.
여기까지 읽다가 전에 백준에서 못풀었던 이진 탐색법 문제에 대한 영감이 떠올라서 한 번 풀어봐야겠다.
x이상이면 x에 포함된다 이 문제 조건이 왜 존재하는지 정말 이해가 안됐는데 이렇게 보니 "P(right) = true"를 만족하는 최소정수라는 새삼 더 와닿는다. 아 이제는 풀 수 있을 것 같아서 뭔가 설렌다~
:)