알고리즘 :: 구름 - Binary Search #JavaScript

알고리즘 공부하며 배운내용

 

 

구름 - Binary Search

이진 탐색으로 찾고 싶은 수를 찾자

 

이진 탐색 알고리즘

리스트의 중간의 값을 임의로 선택, 찾고자 하는 값과 비교

만약 찾고자 하는 값이 크면(mid < target), 중간이 가장 작은 값이 된다.

만약 찾고자 하는 값이 작다면(mid > target), 중간이 가장 큰 값이 된다.

 

검색이 반복될 때 마다 값을 찾을 확률은 2배가 된다. 속도가 빠르다

 

단점은 정렬된 리스트에만 사용할 수 있다.

 

 

들어오는 값

첫 줄에 배열의 크기

둘 째줄에 수가 오름차순으로

셋 째줄에 찾고자 하는 수

예)

5
1 5 7 9 10
9

 

구하고 싶은 값

찾고하 하는 값이 들어온 수에서 몇 번째에 있는지 출력

예)

4

 

 

생각

구름 설명대로 찬찬히 따라가보자

 

 

코드

오늘도 좀 정신사납지만 완료

const readline = require("readline");
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
});

let input = []
rl.on("line", function(line) {
	if(!line) {
		rl.close()
	}
	else {
		input.push(line)
	}
}).on("close", function() {
	bi(input)
	process.exit();
});

function bi(base) {
	let [size, num, tar] = base
	num = num.split(' ').map(Number)
	let arr = [...num]
	let min = arr[0]
	let max = arr[+size - 1]
	let mid = arr[Math.floor(size / 2)]
	let answer = 'X'
	
	while(arr.length > 2) {
		if(mid === +tar) {
			answer = num.indexOf(mid) +1
			break;
		}
		else if(mid < +tar){
			arr = arr.slice(Math.floor(arr.length) / 2)
			min = arr[0]
			mid = arr[Math.floor(arr.length / 2)]
		}
		else {
			arr = arr.slice(0, Math.floor(arr.length) / 2)
			max = arr[mid]
			mid = arr[Math.floor(arr.length / 2)]
		}
	}
	console.log(answer)
}