이진 탐색(Binary Search) start, end mid(인덱스)!!
이진 탐색은 정렬된 배열에서 특정 값 key를 찾는 알고리즘이다. 배열이 오름차순으로 정렬되어 있다고 할 때 key와 중간값을 비교한뒤 작으면 배열의 왼쪽 반에서, 크면 배열 오른쪽 반에서 다시 key를 찾는다. 계속 반으로 나눠가며 찾기 때문에 시간복잡도는 O(log2n)이다.
static int binS(int[] arr, int key)
{ // 반복문 사용
int start = 0;
int end = arr.length - 1;
int mid;
while(start <= end)
{
mid = (start + end) / 2;
if (arr[mid] == key)
return mid;
else if (key < arr[mid])
{
end = mid - 1;
}
else
start = mid + 1;
}
return -1;
}
static int binSR(int[] arr, int start, int end, int key)
{ // 재귀 사용
if (start > end)
return -1;
int mid = (start + end) /2;
if (arr[mid] == key)
{
return mid;
}
else if (key < arr[mid])
{
return binSR(arr, start, mid-1, key);
}
else
{
return binSR(arr, mid+1, end, key);
}
}
삼진 탐색은 이와 유사하게 배열을 계속 3등분하여 key를 찾는 것이다.
배열을 n/3개의 숫자들을 가진 3개의 부분배열로 분할하면서 key를 탐색한다. 이진 탐색에선 중간값(mid)가 하나였지만, 삼진 탐색은 중간값이 두개가 필요하다.(mid1, mid2)
따라서 구간을 나눠보면 다음과 같다.
|---A---|---B---|---C---|
mid1 mid2
코드로 나타내면
public int tri(int[] arr, int start, int end, int key)
{
if (start > end)
return -1;
int mid1 = start + (end - start + 1) / 3; // mid1. 앞쪽에 n/3개
int mid2 = end - (end - start + 1) / 3; // mid2. 뒷쪽에 n/3개
if (arr[mid1] == key)
return mid1;
else if (arr[mid2] == key)
return mid2;
else if (key < arr[mid1]) // A구간
return tri(arr, start, mid1-1, key);
else if(key > arr[mid2]) // C구간
return tri(arr, mid2+1, end, key);
else // B구간
return tri(arr, mid1+1, mid2-1, key);
}이 문제에서 입력 크기는 배열의 크기인 n이고 기본연산은 key를 두 중간값과 비교하는 것이다. 첫 시행 후에는 배열이 1/3만 남아 n/3, 두번째 시행 후에는 그 배열이 또 1/3만 남아 1/3 n/3, 세번째 시행 후에는 그 배열이 또 1/3만 남아 1/3 1/3 n/3 … 이런 식으로 k번 실행 후에는 (1/2)^k n개가 남게 된다. 마지막에 남는 것은 1개이므로 (1/2)^k * n = 1이라고 했을 때 k=log3n이 된다. 즉 시간 복잡도는 O(log3N)이다.
