이진 탐색 알고리즘은 정렬된 리스트의 값들 중 특정 값을 찾을 때 사용할 수 있는 상당히 빠른 알고리즘이다.
간략히 요약하자면, 왼쪽 인덱스와 오른쪽 인덱스를 기준으로 그 정 중앙의 값과 찾고자하는 값을 비교한다.
만약 중앙값이 더 크다면 왼쪽 인덱스를 중앙인덱스+1로, 더 작다면 오른쪽 인덱스를 중앙인덱스-1을 하며 거리를 점점 좁혀나간다. 여기서 +1 -1을 하는 이유는 이미 확인한 중앙값이 찾고자하는 값이 아니므로 그 인덱스를 배제하기 위함이다.
이진 탐색의 시간복잡도는 O(logN)이다.
이진 탐색으로 특정 값을 찾는 알고리즘은 다른 많은 블로그에서 정말 잘 설명해주셨기 때문에 이부분은 생략하고, 여기서는 이진 탐색으로 최댓값, 최솟값을 구하는 법에 대해 기록하고자 한다.
이진 탐색 응용(최댓값 / 최솟값)
최댓값, 최솟값은 다른 말로 천장값와 바닥값라고도 불린다.
주어진 숫자보다 작은 수 중 가장 큰 수를 천장값, 주어진 숫자보다 큰 수 중 가장 작은 수를 바닥값라고 한다.
예를 들어 { 1, 3, 5, 7, 9 } 라는 리스트가 있는데, 6이라는 값이 주어졌다고 해보자.
여기서 천장값, 즉 6보다 작은 값들 중의 최댓값은 5가 된다.
그리고 바닥값는 반대로 6보다 큰 값들 중의 최솟값이므로 7이 된다.
이분 탐색을 활용하면 최솟값과 최댓값도 쉽게 구할 수 있다.
개인적으로 이 부분을 구현하는데 많이 혼란스러웠기 때문에 간단한 코드로 기록하여 쉽게 이해해보자.
코드
int[] list = {1, 3, 5, 7, 9};
int num = 6;
int start = 0; //왼쪽 인덱스
int end = 4; //오른쪽 인덱스
while(start <= end) {
int mid = (start + end) / 2;
if(num < list[mid]){
end = mid - 1;
}
else if(num > list[mid]) {
start = mid + 1;
}
}
System.out.println("최댓값 : " + list[end]);
System.out.println("최솟값 : " + list[start]);
위 코드에서는 주어진 값이 리스트 안의 값과 일치하는 경우는 생략하였다.
반복문을 사용하여 이진 탐색을 구현하였고, start, end의 값을 계속해서 갱신하는 방식으로 진행하였다.
end는 주어진 값보다 작은 값들로 계속 탐색해 나가고, start는 주어진 값보다 큰 값으로 계속 탐색해간다. 따라서 mid -1, mid +1의 코드를 통해 mid로 확인한 값은 제외한다.
계속 진행하다보면 start와 end가 주어진 값 num을 기준으로 엇갈리게 된다. 마지막에 end는 리스트 값 중 5를, start는 7을 가리키게 될 것이다. 그 의미는 end는 최댓값을, start는 최솟값을 찾았다는 의미이니 두 경우를 모두 찾은 셈이 된다.
다만 위 코드는 리스트에 num과 일치하는 값이 없다는 전제가 있을 때 동작한다.
그렇다면 만약 리스트에 num과 일치하는 값이 있고, 최대 혹은 최솟값을 구한다면 어떻게 해야할까?
위 코드를 조금 변형하면 쉽게 찾을 수 있다
1. 최솟값
public class Test {
public static void main(String[] args) {
int[] list = {1, 3, 5, 7, 9};
int num = 5;
int start = 0; //왼쪽 인덱스
int end = 4; //오른쪽 인덱스
while(start < end) {
int mid = (start + end) / 2;
if(num < list[mid]){
end = mid - 1;
}
else if(num >= list[mid]) {
start = mid + 1;
}
}
System.out.println("최솟값 : " + list[start]);
}
}
최솟값의 요점은 다음과 같다
- start가 최솟값을 탐색한다
- start는 '주어진 숫자와 일치하지 않는' 최솟값을 찾는 것이기 때문에 mid값을 건너 뛰어야 한다(mid+1)
- start는 '주어진 숫자보다 큰 값들' 중의 최솟값을 찾기 때문에 mid 값이 num보다 작거나 '같으면' 값을 갱신한다
최댓값은 이와 반대로 작성하면 된다
정정사항에 대한 피드백은 늘 환영입니다.
