이진 탐색(Binary Search)

이진 탐색은 우리가 배열에서 특정한 값을 찾고자 할 때 사용하는 알고리즘이다.

자바스크립트에서 특정한 값의 인덱스를 모른다고 했을 때 그 특정한 값을 찾기 위해서 일반 for문즉 선형적 탐색을 사용할 경우 O(n) 만큼의 시간이 걸린다. 여기서 n은 배열의 길이 만큼이다. 최악의 경우 찾고자 하는 값이 배열의 맨 끝에 존재할 경우 배열의 길이만큼 시간이 걸린다. 이진 탐색은 특정한 값을 기준 root로 특정한 값보다 작으면 왼쪽 자식 노드, 특정한 값보다 크면 오른쪽 자식 노드로 형성된 이진 트리에서 값을 찾는데 걸리는 시간은 최악의 경우에도 O(log n)이 걸린다.

아래의 그림을 보면 이해가 쉽다.

위 그림은 8을 루트로 8보다 작은 3은 왼쪽 10은 오른쪽 자식으로 지정하고 다시 그 3 과 10 에서 다시 본인보다 작으면 왼쪽 자식, 크면 오른쪽 자식으로 분류하고 있다.

위 그림을 배열로 만들 수 있다.

let Binary_tree = [null ,8 ,3 ,10 ,1 ,6 ,null ,14 ,null ,null ,4 ,7 ,null null 13]
								//[0     1  2  3   4  5   6    7    8     9    10 11  12   13  14] <- 배열의 인덱스

								//여기서 root는 1번째 인덱스 8

위 배열에서 0번째 인덱스는 null로 취급 해 줬다. 그 이유는 우리가 자식 노드를 정할 때 부모 노드의 index 를 기준으로 왼쪽 자식 노드, 오른쪽 자식 노드를 정할 때 0부터 계산하면 귀찮기 때문이다. 부모 노드의 인덱스를 i 라 할 때

(i x 2) 는 왼쪽 자식 노드

(i x 2) + 1 은 오른쪽 자식 노드

이다. 보통 root는 arr[Math.floor(arr.length/2)]즉 배열의 중간 인덱스로 정한다.

위와 같이 이진 트리로 만든 후 특정한 값을 찾고자 할 때 root 부터 찾고자 하는 특정한 값과 비교해 나간다.

찾고자 하는 값 = 6 라 할 때 처음부터 8과 비교해서 8보다 작으니 왼쪽 자식 노드 3과 비교하고 3보다 크니 3의 오른쪽 자식인 6 이렇게 값을 찾는다.

이진 탐색(Binary Search) 자바스크립트로 구현

let arr = [3,10,6,14,8,13,1,4,7]                //정렬되지 않은 배열

function MakeBinaryTree(arr) {
	let BT = [];                                 //BT(BinaryTree)
	BT[1] = arr[Math.floor(arr.length/2)];       //BT의 root는  
	
		this.sort = function () {
			for(let i = 0 ; i < arr.length; i++){
					let node = 1;
					while(1) {
						if(arr[i] > BT[node] && BT[node*2+1] == undefined) {
							BT[node*2+1] = arr[i]
							break;
						} else if (arr[i] < BT[node] && BT[node*2] == undefined) {
							BT[node*2] = arr[i];
							break;
						} else if (arr[i] > BT[node] && BT[node*2+1] != undefined){
							node = node*2 + 1
						} else if (arr[i] < BT[node] && BT[node*2] != undefined) {
							node = node*2;
						} else {
	            break;
	          }
					}
			}
		}
	
    this.insert = function (num) {
      let node = 1;
			while(1) {
		    if(num > BT[node] && BT[node*2+1] == undefined) {
		    	BT[node*2+1] = num
			    break;
				} else if (num < BT[node] && BT[node*2] == undefined) {
					BT[node*2] = num
					break;
				} else if (num > BT[node] && BT[node*2+1] != undefined){
					node = node*2 + 1
				} else if (num < BT[node] && BT[node*2] != undefined) {
					node = node*2;
				} else {
          break;
        }
			}
    }

		this.findvalue = function (num) {
			let node = 1;
			while(node < BT.length) {
				if(num < BT[node]  && BT[node] != undefined) {
					node = node*2;
				} else if(num > BT[node] && BT[node] != undefined) {
					node = node*2+1;
				} else {
					break;
				}
			}
			if(BT[node] == num) {
				return 1;
			} else {
				return 0;
			}
		}

		this.show = function () {
			console.log(BT);
		}
}

let new_arr = new MakeBinaryTree(arr);                  
new_arr.sort();                                         //arr를 이진트리로 새롭게 정렬
console.log(new_arr.findvalue(13))                      //1출력
console.log(new_arr.findvalue(1))                       //1출력
console.log(new_arr.findvalue(5))                       //0출력
console.log(new_arr.insert(5));                         //5를 넣고 재정렬 
console.log(new_arr.findvalue(5))                       //1출력
console.log(new_arr.show())                             
//[undefiend ,8 ,3 ,10 ,1 ,6 ,undefined ,14 ,undefined * 2 ,4 ,7 ,undefined * 2 ,13 ,undefined * 6, 5];

삭제 기능은 넣지 못했다. 삭제할 녀석의 자식 노드가 없는 경우에는 그것만 제외하면 정말 간단하지만, 자식 노드가 하나 일 경우, 두 개 일 경우, 그 자식의 자식 노드가 또 한 개 일 경우 등.. 너무 복잡해질 것 같아서 이 정도만 구현 했습니다.

위에 코드를 보면 쓸데없이 길고 그냥 선형적으로 for문으로 탐색하면 안되나 싶겠지만, 데이터 양이 많아 질때 효율적인 서치를 위해 이진탐색알고리즘을 사용하는 것이 좋습니다.

예시로는 "주소록에서 특정 이름을 찾기"입니다. 예를 들어, 사용자가 주소록에 등록된 사람의 이름을 검색하고자 할 때, 이진 탐색은 효율적인 검색 방법으로 사용될 수 있습니다.

주소록은 일반적으로 알파벳순으로 정렬되어 있으며, 이진 탐색을 사용하여 특정 이름을 빠르게 찾을 수 있습니다. 이진 탐색은 중간 위치의 이름과 찾고자 하는 이름을 비교하여 찾고자 하는 이름이 위치한 범위를 좁혀가며 탐색을 수행합니다. 이렇게 반복하여 이름을 찾을 때까지 탐색을 진행하면 효율적으로 결과를 얻을 수 있습니다.

위 코드가 어떻게 작동하는지 직접 눈으로 보고 싶으면 아래의 사이트를 참고해주시면 됩니다.

https://visualgo.net/en/bst