[이분탐색]
이분탐색은 얼핏보면 쉬어 보이지만, 조금만 더 들어가 보면 꽤 까다롭다.
아래 5가지로 분류된 이분탐색 응용분야를 꼼꼼이 살펴보고 코딩 및 결과 차잇점을 음미해야 한다.
- 이분탐색 : 일반적인 이분탐색. 찾은 인덱스 리턴. 못 찾으면 -1 리턴
- 이분탐색_최소인덱스: 찾으려는 값에 대해 여러 개 있을 경우, 가장 작은 인덱스(왼쪽 편) 리턴. 없으면 -1 리턴
- 이분탐색_최대인덱스: 찾으려는 값에 대해 여러 개 있을 경우, 가장 큰 인텍스(오른 편) 리턴. 없으면 -1 리턴
- Lower_Bound: 찾으려는 목표값 k 이상되는 수가 처음 나타나는 위치 리턴.
- Upper_Bound: 찾으련는 목표값 k 보다 큰 수가 처음 나타나는 위치 리턴
예를 들어 a[6]={3,5,5,5,6,16} 같은 배열이 있을 때, {1,3,4,5,8,16,18}을 차례로 찾아보면 어떻게 될까?
아래표와 같이 해당 인덱스를 찾게 된다.
|
i |
0 |
1 |
2 |
3 |
4 |
5 |
|
a[i] |
3 |
5 |
5 |
5 |
6 |
16 |
|
k |
binary |
bi_first |
bi_last |
lower |
upper |
|
1 |
-1 |
-1 |
-1 |
0 |
0 |
|
3 |
0 |
0 |
0 |
0 |
1 |
|
4 |
-1 |
-1 |
-1 |
1 |
1 |
|
5 |
2 |
1 |
3 |
1 |
4 |
|
8 |
-1 |
-1 |
-1 |
5 |
5 |
|
16 |
5 |
5 |
5 |
5 |
5 |
|
18 |
-1 |
-1 |
-1 |
5 |
5 |
하나 씩 살펴보자.
이분탐색
이분탐색은 정렬된 상태의 배열에서 특정 값 k의 위치를 logN의 수행시간에 찾을 수 있는 방법이다.
원리는, 배열의 절반 위치에 있는 값과 k와의 대소관계를 따져서, 작은 쪽인 왼쪽 혹은 큰 쪽인 오른쪽 편에서 찾는 작업을 계속 진행.
//[s,e]사이에서 a[i]==k인 i 리턴. 없으면 -1 리턴
//s: start index, e:end index, k: target value
int binary_search(int s, int e, int k){
int m;
while(s<=e){
m = (s+e)/2;
if(k==a[m]) return m;
if(k>a[m]) s=m+1;
else e=m-1;
}
return -1;
}
이분탐색_최소인덱스
단순한 이분 탐색의 경우, 찾으려는 값이 여러개 있는 경우, 처음 찾은 목표값 인덱스를 그대로 리턴한다. 근데 만약 여러 개 있는 값 중에서 가장 인덱스가 작은 것을 리턴하고자 한다면 어떻게 할까?
아래 코드처럼, 목표값을 찾았을 때 바로 리턴하지 않고, (e=m-1)로 놔서 더 왼쪽편에도 목표값이 있는 지 찾게하면 된다.
//[s,e]사이에서 a[i]==k인 i 리턴. 없으면 -1 리턴
//s: start index, e:end index, k: target value
int binary_search_first(int s, int e, int k){
int m, ans=-1;
while(s<=e){
m = (s+e)/2;
if(k==a[m]) {
ans=m;
e=m-1;
}else if(k>a[m]) s=m+1;
else e=m-1;
}
return ans;
}
이분탐색_최대인덱스
찾으려는 값이 여러개 존재하는데, 이 중에서 가장 큰 인덱스를 리턴하고자 한다면, 목표값을 발견했을 때 (s=m+1)로 놔서, 오른편에도 찾으려는 값이 있는 지 더 찾아보게하면 된다.
int binary_search_last(int s, int e, int k){
int m, ans=-1;
while(s<=e){
m = (s+e)/2;
if(k==a[m]) {
ans=m;
s=m+1;
}else if(k>a[m]) s=m+1;
else e=m-1;
}
return ans;
}
Lower_Bound
이분탐색처럼
//[s,e)사이에서 a[i]>=k가 처음되는 i값 리턴.
//모든 a[i]에 대해서 k>a[i]이면 = k>a[e]이면 ==> e 리턴
//모든 a[i]에 대해서 k<a[i]이면 = k<a[s]이면 ==> s 리턴
int lower_bound(int s, int e, int k){
int m;
while(s<e){
m = (s+e)/2;
if(k>a[m]) s=m+1;
else e=m;
}
return e;
}
//[s,e)사이에서 a[i]>k가 처음되는 i값 리턴.
//모든 a[i]에 대해서 k>a[i]이면 = k>a[e]이면 ==> e 리턴
//모든 a[i]에 대해서 k<a[i]이면 = k<a[s]이면 ==> s 리턴
int upper_bound(int s, int e, int k){
int m;
while(s<e){
m = (s+e)/2;
if(k>=a[m]) s=m+1;
else e=m;
}
return e;
}
-끝-