알고리즘 - 이진탐색

이진 탐색

여러분이 보통 탐색에 많이 사용하시는 방법은 선형 탐색입니다. 즉, 순서대로 하나씩 찾는 탐색 알고리즘을 말합니다. O(n)의 시간복잡도가 걸립니다.

하지만 효율성을 높이기 위해서 우리는 정렬 되어있는 요소들을 반씩 제외하며 찾을 수 있습니다. 이것을 이진 탐색이라고 합니다. 이진 탐색은 **O(log n)**만큼의 시간복잡도가 걸립니다.

이진 탐색은 반드시 정렬이 되어 있어야 사용할 수 있으며, 만약 정렬이 되어있지않다면 선형탐색보다 더 많은 시간이 걸릴 수도 있습니다. 배열 혹은 이진 트리를 이용하여 구현할 수 있습니다.

배열

배열에서 요소를 찾으려면 시작 지점을 left, 끝 지점을 right라고 두며 mid = (left+right)/2 로 중간 지점을 표현합니다. 중간지점과 탐색할 요소를 비교하여 크다면 left를 mid+1로, 작다면 right를 mid-1로 둡니다. 이 과정을 반복해 mid가 탐색요소와 동일할 때까지 탐색합니다. 배열을 이용한 방법은 중간에 요소를 추가하거나 삭제하는 경우 선형시간이 걸릴 수 있습니다.

const array = [1,1,5,124,400,599,1004,2876,8712];

function binarySearch(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;
}

이진 탐색 트리

이진 탐색 트리는 이진 탐색을 위해 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이, 오른쪽 서브 트리는 루트보다 큰 값이 있도록 구성합니다. 요소를 삭제할 때, Leaf Node를 삭제하는 경우에는 별다른 처리 없이 부모와의 연결을 끊어주면 됩니다. 만약, 하나의 서브 트리를 갖는 경우 제거되는 정점의 부모 간선이 자식을 가리키도록 합니다. 만약, 두 개의 서브 트리를 갖는 경우 왼쪽 서브 트리의 가장 큰 값, 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 됩니다. 이 경우 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체됩니다. 이진 탐색 트리는 최악의 경우 한쪽으로 편햔된 트리가 될 수 있으며, 그 경우 순차 탐색과 동일하게 선형 시간이 걸릴 수 있습니다. 이를 해결하기 위해 AVL 트리 혹은 레드-블랙 트리를 사용합니다.

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

class BinarySearchTree{
	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;
	}
}