📌 Intro
데이터를 탐색하는 알고리즘 중 가장 기본적인 알고리즘은 순차 탐색이다. 하지만 순차 탐색은 최악의 경우 O(N) 시간 복잡도를 가지고 있기 때문에 상당히 느리다.
이보다 조금 더 빠르게 탐색하는 방법인 이진 탐색 알고리즘에 대해서 알아보도록 하자.
📌 이진 탐색(Binary Search)
이진 탐색은 데이터가 정렬되어 있는 경우에만 사용할 수 있는 탐색 방법이다. 탐색 범위를 절반씩 줄여가면서 탐색을 진행한다.
이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점 이다. 찾으려는 데이터와 중간점의 데이터를 반복적으로 비교하여 탐색의 범위를 줄여나가고 원하는 데이터를 찾는 것이 이진 탐색 과정이다.
STEP 0
이미 정렬된 10개의 데이터 중 값이 17인 원소를 찾는 예시를 통해 더 깊이 이해해보도록 하자. 초기의 탐색 범위는 시작부터 끝이다. 중간점의 위치는 (0 + 9) / 2 = 4.5 → 4번째 인덱스에 위치한 12가 된다.
STEP 1
중간점의 값이 찾는 값보다 작기 때문에 시작점의 위치는 중간점 다음으로 바꿔주도록 한다. 찾는 값이 중간점에 위치한 값보다 크고, 이미 데이터는 정렬된 상태이기 때문에 중간점보다 앞에 위치한 값들은 살펴볼 필요가 없는 것이다.
시작점의 위치가 바뀌었기 때문에 중간점의 위치도 바뀌는데 (5 + 9) / 2 = 7번째 인덱스에 위치한 24가 된다.
STEP 2
중간점의 값이 찾는 값보다 크기 때문에 끝점의 위치는 중간점 이전으로 바꿔주도록 한다. 찾는 값이 중간점에 위치한 값보다 작고, 이미 데이터는 정렬된 상태이기 때문에 중간점보다 뒤에 위치한 값들은 살펴볼 필요가 없는 것이다.
끝점의 위치가 바뀌었기 때문에 중간점의 위치도 바뀌는데 (5 + 6) / 2 = 5.5 → 5번째 인덱스에 위치한 15가 된다. 시작점과 중간점의 위치가 같아졌지만 크게 신경쓰지 않아도 된다.
STEP 3
중간점의 값이 찾는 값보다 크기 때문에 시작점의 위치는 중간점 다음으로 바꿔주도록 한다.
시작점의 위치가 바뀌었기 때문에 중간점의 위치도 바뀌는데 (6 + 6) / 2 = 6번째 인덱스에 위치한 17가 된다. 원하는 값을 찾았기 때문에 이진 탐색을 종료한다.
📌 이진 탐색 구현
#include <iostream>
using namespace std;
int arr[10] = { 1, 3, 4, 5, 7, 9, 12, 13, 15, 18 }; // 데이터들이 크기순으로 졍렬되어 있는 상태
int binarySearch(int target) {
int start = 0;
int end = 9;
int mid = (start + end) / 2;
while (start < end) {
mid = (start + end) / 2;
if (arr[mid] > target) {
end = mid - 1;
}
else if (arr[mid] < target) {
start = mid + 1;
}
else {
return mid;
}
}
return end;
}
int main() {
int index = binarySearch(5);
cout << index;
return 0;
}📌 관련 문제
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
📌 More Details
아래 문제를 풀다가 알게 된 것인데 이진 탐색을 단순히 원하는 값을 찾는 것이 아니라 원하는 값의 범위를 찾는데에도 사용할 수 있다.
10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
Lower Bound
Lower Bound는 원하는 값 K 이상의 값이 처음 나오는 위치이다. Lower Bound의 계산 과정은 이진 탐색과 별 다를것 없이 비슷하다.
1, 3, 5, 7, 9, 11 의 데이터에서 9 이상의 값이 처음으로 나오는 위치를 구하는 과정을 예로 들어보자.
STEP 0
시작점은 1을, 끝점은 11을, 중간점은 5를 가리키고 있다.
STEP 1
중간점의 값보다 찾는 값이 크기 때문에 시작점의 위치는 5다음인 7이 된다. 시작점이 바뀌었기 때문에 중간점 역시 9를 가리키도록 바뀔 것이다.
STEP 2
중간점의 값과 찾는 값이 같기 때문에 끝점의 위치는 9가 된다. 끝점이 바뀌었기 때문에 중간점 역시 7을 가리키게 될 것이다.
STEP 3
중간점의 값보다 찾는 값이 작기 때문에 시작점의 위치는 7다음인 9가 된다. 시작점의 위치와 끝점의 위치가 같아졌기 때문에 이진 탐색은 종료한다.(조금 더 정확하게 이야기하면 끝점의 위치가 시작점의 위치보다 크지 않기 때문에 종료하는 것이다.)
소스코드로 구현한다면 다음과 같을 것이다.
#include <iostream>
using namespace std;
int arr[6] = { 1, 3, 5, 7, 9, 11 }; // 데이터들이 크기순으로 졍렬되어 있는 상태
int lowerBound(int target) {
int start = 0;
int end = 5;
int mid = (start + end) / 2;
while (start < end) {
mid = (start + end) / 2;
if (arr[mid] >= target) { // 중간값이 원하는 값보다 크거나 같을 경우 끝 값을 중간값으로 설정하여 다시 탐색
end = mid;
}
else { // 중간값이 원하는 값보다 작을 경우 시작 값을 중간값+1로 설정하여 다시 탐색
start = mid + 1;
}
}
return end;
}
int main() {
int lowerBoundIndex = lowerBound(9);
cout << lowerBoundIndex;
return 0;
}Upper Bound
Upper Bound는 원하는 값 K를 초과한 값이 처음 나오는 위치이다. Lower Bound에서 조건 하나만 바꾸면 찾을 수 있다.
1, 3, 5, 7, 9, 11 의 데이터에서 9 이상의 값이 처음으로 나오는 위치를 구하는 과정을 예로 들어보자.
STEP 0
시작점의 값은 1, 끝 점의 값은 11, 중간점의 값은 5가 될 것이다.
STEP 1
중간점의 값보다 찾는 값이 크기 때문에 시작점의 위치는 5다음인 7이 된다. 시작점이 바뀌었기 때문에 중간점 역시 9를 가리키도록 바뀔 것이다.
STEP 2
중간점의 값과 찾는 값이 같기 때문에 시작점의 위치는 9다음인 11이 된다. 끝점의 위치가 시작점의 위치보다 크지 않기 때문에 이진 탐색은 종료된다.
소스코드로 구현한다면 다음과 같을 것이다.
#include <iostream>
using namespace std;
int arr[6] = { 1, 3, 5, 7, 9, 11 }; // 데이터들이 크기순으로 졍렬되어 있는 상태
int upperBound(int target) {
int start = 0;
int end = 5;
int mid = (start + end) / 2;
while (start < end) {
mid = (start + end) / 2;
if (arr[mid] > target) { // 중간값이 원하는 값보다 클 경우 끝 값을 중간값으로 설정하여 다시 탐색
end = mid;
}
else { // 중간값이 원하는 값보다 작거나 같을 경우 시작값을 중간값+1로 설정하여 다시 탐색
start = mid + 1;
}
}
return end;
}
int main() {
int upperBoundIndex = upperBound(9);
cout << upperBoundIndex;
return 0;
}
Lower Bound와 Upper Bound를 구하는데 있어 코드의 차이점은 arr[mid]와 target을 비교하는 부분에서 등호를 빼주면 된다.
📌 참고
[1] 이것이 취업을 위한 코딩 테스트다 with 파이썬
[2] https://blog.naver.com/bestmaker0290/220820005454
