［Algorithm］이진탐색 알고리즘(Binary Search Algorithm)
이진탐색
- 정의
- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 것.
- 오름차순으로 정렬된 리스트일 경우에만 사용할 수 있다는 단점이 있지만, 절반씩 줄여가며 탐색하기 때문에 매우 빠르다.
- 구현
- 해당 배열에서 가운데 값을 찾고, 그 값과 비교하여 해당 인덱스에서의 배열의 값이 찾는 값 보다 클때는 앞쪽에서 찾고, 작을때는 뒤쪽에서 찾으면 된다.
- 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// 해당 인덱스를 출력해주는 알고리즘 입니다.
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
참고자료
［Algorithm］이진탐색 알고리즘(Binary Search Algorithm)
