［Algorithm］이진탐색 알고리즘(Binary Search Algorithm)

hodory included in categories ETC Algorithm

2018-04-19 2018-04-19 308 words One minute

Contents

이진탐색

정의
- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 것.
- 오름차순으로 정렬된 리스트일 경우에만 사용할 수 있다는 단점이 있지만, 절반씩 줄여가며 탐색하기 때문에 매우 빠르다.

구현
- 해당 배열에서 가운데 값을 찾고, 그 값과 비교하여 해당 인덱스에서의 배열의 값이 찾는 값 보다 클때는 앞쪽에서 찾고, 작을때는 뒤쪽에서 찾으면 된다.
- 코드

// 해당 인덱스를 출력해주는 알고리즘 입니다.
binarSearch = (data, value) => {
	let start = data[0], end = data.slice(-1)[0], index = 0, last = data.length-1
	if (value < start || value > end)
		return -1;
	while (index <= last) {
		let center = parseInt((index+last) / 2)
		if (data[center] === value)
			return center;
		else if(data[center] > value)
			// 해당 인덱스의 배열값이 더 크기때문에 최대 인덱스를 줄인다.
			last = center - 1
		else
			// 해당 인덱스의 배열값이 더 작기때문에 최소 인덱스를 늘린다.
			index = center + 1
    }
}

// 호출
binarSearch([1,5,7,11,25],25) // 4
binarSearch([1,5,7,11,14,16,18,25],18) // 6

참고자료