⚡ 알고리즘 - 이진 탐색, 해시 탐색, BST

🔹 이진 탐색(Binary Search)

▫️ 개념

• 정렬된 배열에서 중간값과 찾는 값을 비교하여 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는 알고리즘

▫️ 시간 복잡도

• 평균, 최악: O(log n)
• 공간 복잡도: O(1)

▫️ 특징

• 배열이 반드시 정렬되어 있어야 함
• 빠른 탐색 속도

▫️ 예제 코드

public class BinarySearch {
	public static int binarySearch(int[] arr, int target) {
		int left = 0, right = arr.length - 1;
		
		while (left <= right) {
			int mid = left + (right - left) / 2;
			
			if (arr[mid] == target) return mid;
			else if (arr[mid] < target) left = mid + 1;
			else right = mid - 1;
		}
		
		return -1; // 못 찾았을 때
	}
	
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 6, 8, 10};
		System.out.println(binarySearch(arr, 6)); // 3
	}
}

🔹 해시 탐색(Hash)

▫️ 개념

• 키를 해시 함수에 입력해 고유한 인덱스를 계산하고, 해당 위치에 값을 저장 또는 검색하는 탐색 방법

▫️ 시간 복잡도

• 평균: O(1)
• 최악: O(n) (해시 충돌 발생 시)

▫️ 특징

• 빠른 삽입 및 검색 가능
• 충돌 처리 방법 (체이닝, 오픈 어드레싱 등) 필요

▫️ 예제 코드

import java.util.HashMap;

public class HashSearch {
	public static void main(String[] args) {
		HashMap<String, Integer> map = new HashMap<>();
		map.put("apple", 5);
		map.put("banana", 3);
		
		System.out.println(map.get("apple")); // 5
		System.out.println(map.get("grape")); // null
	}
}

🔹 트리 기반 탐색 (Binary Search Tree, BST)

▫️ 개념

• 이진 탐색 트리(BST)는 왼쪽 서브트리에 작은 값, 오른쪽 서브트리에 큰 값이 위치하는 이진 트리 구조에서 값을 탐색하는 방법

▫️ 시간 복잡도

• 평균: O(log n)
• 최악: O(n) (트리가 한쪽으로 치우친 경우)

▫️ 특징

• 정렬된 데이터의 효율적 탐색, 삽입, 삭제 가능
• 균형 트리 (AVL, Red-Black Tree) 사용 시 최악 성능 개선

▫️ 예제 코드

class Node {
	int key;
	Node left, right;
	Node(int item) {
		key = item;
		left = right = null;
	}
}

public class BST {
	Node root;
	
	public void insert(int key) {
		root = insertRec(root, key);
	}
	
	private Node insertRec(Node root, int key) {
		if (root == null) {
			root = new Node(key);
			return root;
		}
		if (key < root.key) root.left = insertRec(root.left, key);
		else if (key > root.key) root.right = insertRec(root.right, key);
		return root;
	}
	
	public boolean search(int key) {
		return searchRec(root, key);
	}
	
	private boolean searchRec(Node root, int key) {
		if (root == null) return false;
		if (root.key == key) return true;
		if (key < root.key) return searchRec(root.left, key);
		return searchRec(root.right, key);
	}
	
	public static void main(String[] args) {
		BST tree = new BST();
		tree.insert(50);
		tree.insert(30);
		tree.insert(70);
		System.out.println(tree.search(30)); // true
		System.out.println(tree.search(90)); // false
	}
}

🔹 비교

알고리즘	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도	특징
이진 탐색	O(log n)	O(log n)	O(1)	정렬된 배열에서만 사용 가능, 빠른 탐색
해시 탐색	O(1)	O(n)	O(n)	빠른 삽입/검색, 해시 충돌 처리 필요
트리 탐색 (BST)	O(log n)	O(n)	O(n)	정렬 데이터 탐색 가능, 균형 트리로 성능 개선 가능