알고리즘 분석 | Linked Structure | 이진 탐색 알고리즘 구현

이전 포스팅

알고리즘 분석 | 데이터 구조 Rooted Tree | Tree ADT | 전위, 중위, 후위 순회

링크드 구조(Linked Structure)

링크드 구조는 각 노드가 자신이 저장하는 요소와 부모 및 자식 위치의 위치를 참조하는 객체로 표시되는 데이터 구조입니다. 즉, 각 노드는 해당 노드와 부모, 자식 노드를 가리키는 포인터(참조)들을 포함하고 있는 구조입니다. 이러한 구조를 사용하여 트리와 같은 계층적 데이터 구조를 나타낼 수 있습니다

 

예를 들어, 이진 트리(binary tree)를 살펴보겠습니다. 루트는 A[0]에 저장됩니다. 루트의 (있을 수 있는) 두 자식은 A[1]과 A[2]에 저장됩니다. A[1]의 두 자식은 A[3]과 A[4]에 저장되며, A[2]의 두 자식은 A[5]와 A[6]에 저장됩니다. 이와 같은 방식으로 계속해서 배열 A에 저장됩니다.

 

이러한 배열 표현을 사용하면, 트리의 각 노드를 일반적인 방법으로 순회하거나 검색하는 대신, 각 노드의 위치를 배열 인덱스로 바로 참조할 수 있습니다. 따라서 특정 노드를 찾는 데 \(O(n)\)시간이 걸리는 일반적인 트리 탐색 알고리즘보다 훨씬 효율적으로 작업할 수 있습니다

 

트리 자료 구조

1. 루트 노드가 주어지고, 각 노드가 최대 \(t\)개의 자식을 가지고 깊이가 유한한 트리를 배열에 저장할 수 있습니다.
2. 이진 트리의 경우, 배열에서 노드 \(A[i]\)의 왼쪽 자식은 \(A[2 * i + 1]\), 오른쪽 자식은 \(A[2 * i + 2]\)에 저장됩니다. 부모 노드는 \(A[⌊(i - 1)/2⌋]\)에 위치합니다.
3. 이러한 배열 표현은 일반적인 트리 구조에서 배열 기반 자료 구조로 변환을 가능하게 하고, 배열 인덱스를 사용하여 노드에 더욱 효율적으로 접근할 수 있습니다

예를 들어, t-ary tree의 경우, 노드 \(A[i]\)의 자식들은 \(A[ti+1], A[ti+2], ..., A[ti+t]\)에 저장됩니다. 부모 노드는 \(A[⌊(i-1)/t⌋]\)에 위치합니다

---

 

이진 탐색(Binary Search)

이진 탐색(Binary Search)은 정렬된 배열에서 값을 찾는 알고리즘입니다. 이진 탐색은 배열의 중간값을 기준으로 찾고자 하는 값이 중간값보다 큰지 작은지를 판별하여 해당 구간을 반으로 쪼개면서 값을 찾아 나갑니다. 이진 탐색에서는 배열에서의 검색 작업만 가능하며, 최악의 경우 시간 복잡도는 O(log n)이 됩니다

 

구현

public static int binarySearch(int[] s, int target) {	
	int low = 1;
	int high = s.length;
		
	while(low<=high) {
		int mid = (low + high)/2;
		if(s[mid] == target) {
			return mid;   // 7의 인덱스 값 반환
		}else if(s[mid] < target){
			low = mid + 1;
		}else {
			high = mid - 1;
		}	 
	}
	return -1;
}

public static void main(String[] args) {
	int[] a = {1,2,3,4,5,6,7,8,9,10};	
	System.out.println(binarySearch(a, 7));  // 7이 어디있는지 검색
}
    
출력 : 6

이진 탐색은 주어진 배열이 정렬되어 있다는 가정 하에, 중간값을 기준으로 탐색 범위를 좁혀가며 값을 찾아내는 알고리즘입니다.

 

따라서 low와 high는 각각 탐색 범위의 가장 낮은 인덱스와 가장 높은 인덱스를 가리키며, 이진 탐색을 시작할 때low는 1, high는 배열의 길이로 초기화됩니다.

while문에서는 low와 high가 교차하기 전까지 반복합니다. 이때 mid는 탐색 범위의 중간 인덱스를 가리킵니다. 중간값과 target 값을 비교하여, 중간값이 작으면 low를 증가시켜 범위를 오른쪽으로 좁히고, 중간값이 크면 high를 감소시켜 범위를 왼쪽으로 좁힙니다. mid와 target이 같으면 mid의 인덱스 값을 반환하고 탐색을 종료합니다.

만약 target 값을 찾지 못하면, while문이 종료되고 -1을 반환합니다

 

---