자료구조&알고리즘_이진탐색

이진 탐색

정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
O(log N)만큼 시간복잡도가 걸린다.
ex) Up & Down 게임

이진 탐색 특징

• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열 혹은 이진 트리를 이용하여 구현가능하다.
• 시간복잡도가 O(log N)인 만큼 상당 빠르다.

배열 이진 탐색

• 배열 중간 값을 추가하거나 삭제할 때 선형시간이 걸리는 단점이 있다.
• 그래서 더 효율적인 이진 탐색 트리를 사용한다.

이진 탐색 트리

• 이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고, 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

이진 탐색 트리 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
  ex) 5,4,3,2,1 순으로 추가할 때

이진 탐색 구현 (배열)

const array = [null, 1, 2, 5, 125, 400, 777, 1004, 4563, 7777];

function arrayBinarySearch(array, findValue) {
	let left = 0;
	let right = array.length - 1;
	let mid = Math.floor((left + right) / 2);
	while (left < right) {
		if (array[mid] === findValue) {
			return mid;
		}

		if (array[mid] < findValue) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}

		mid = Math.floor((left + right) / 2);
	}

	return -1;
}

console.log(arrayBinarySearch(array, 1));

이진 탐색 구현 (트리)

class Node {
	constructor(value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

class BinarySearch {
	constructor() {
		this.root = null;
	}

	insert(value) {
		const newNode = new Node(value);
		if (this.root === null) {
			this.root = newNode;
			return;
		}

		let currentNode = this.root;
		while (currentNode !== null) {
			if (currentNode.value < value) {
				if (currentNode.right === null) {
					currentNode.right = newNode;
					break;
				}
				currentNode = currentNode.right;
			} else {
				if (currentNode.left === null) {
					currentNode.left = newNode;
					break;
				}
				currentNode = currentNode.left;
			}
		}
	}

	has(value) {
		let currentNode = this.root;
		while (currentNode !== null) {
			if (currentNode.value === value) {
				return true;
			}

			if (currentNode.value < value) {
				currentNode = currentNode.right;
			} else {
				currentNode = currentNode.left;
			}
		}

		return false;
	}
}

const tree = new BinarySearch();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);

console.log(tree.has(3)); // true
console.log(tree.has(2)); // false

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스