1. 이진 검색 (Binary Search)
ㅇ 실행 방식
- 기 정렬되어있는 순서 리스트에서 만 가능한 검색 방법
- 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법 ☞ 분할 정복법 참조
ㅇ 시간복잡도 : O(log n) ☞ 시간복잡도 표기 예 (로그시간) 참조
- 매번 그 크기를 반씩 줄여나감
. 1번째 (n개), 2번째 (n/2개), 3번째 (n/2 * 1/2), ... , k번째 (n * (1/2)k)
. 마지막 남는 개수를 1로 하면, n*(1/2)k = 1, 2k = n, k = log2 n
ㅇ 적용 : 정렬된 자료 만 가능
2. 이진 검색의 알고리즘 표현 (반복적 구현)
ㅇ 알고리즘의 표현 (by 자바스크립트)
function binarySearchIterative(array, n){
let low = 0;
let high = array.length-1;
while (low <= high) {
let mid = Math.floor( (high + low) / 2 );
// (오버플로우 방지) => mid = low + Math.floor((high - low)/2)
if (n > array[mid]) {
low = mid + 1;
} else if (n < array[mid]) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
- 입력 : array 배열, n 검색할 값
- 출력 : 검색된 위치 인덱스 또는 -1(검색실패)
ㅇ 알고리즘의 단계
- ① 최초 하한은 배열의 첫째값(0), 상한은 배열의 끝값(길이-1)
- ② 상한,하한 사이에 중간값을 찾는 루프
. ⓐ 중간값 지정 (상한,하한의 가운데)
. ⓑ 찾던 값이 중간값 보다 큰지 작은지에 따라,
하한 또는 상한을 하나씩 늘리거나 줄이면서 재지정
. ⓒ 찾던 값이 중간값 이면, 해당 인덱스를 반환하고, 검색 끝냄
- ③ 상한,하한 구간을 반씩 줄여가는 중에 역전되면,
이 배열에 찾는 값이 없는 것이고, -1을 반환
3. 이진 검색의 알고리즘 표현 (재귀적 구현)
ㅇ ... (작성중) ...