선형 검색은 자료를 처음부터 끝까지 순회하며 검색하기 때문에 자료가 클수록 나쁜 효율을 보여줍니다. 그래서 이 단점을 보완하고자 등장한 방식이 이진 검색입니다.
1. 이진 검색
이진 검색(Binary Search)은 일반적으로 선형 검색보다 더 빠른 검색 속도를 보여주는 알고리즘입니다. 단 한가지 전제 조건이 있다면, 이진 검색은 정렬된 컬렉션에 대해서만 검색이 가능하다는 점 입니다. 그래서 정렬 방식에 따라 선형 검색보다 오래걸릴 수도 있습니다.
다음과 같은 배열에서 이진검색을 통해서 26을 검색해보겠습니다.
우선 배열 인덱스의 중앙에 있는 값을 검사합니다. 이 값이 우리가 찾는 키 값 26과 일치하는지 확인합니다. 만약 키 값보다 작다면 배열의 앞 부분을, 키 값보다 크다면 배열의 뒷 부분을 생각하지 않고 나머지 부분에 대해서만 검색을 시도합니다. 왜냐하면 이미 정렬되어있는 배열이기 때문에 더 작거나 큰 부분은 볼 필요가 전혀 없기 때문입니다.
나머지 부분에 대해 다시 한 번 중앙 값을 설정하고 그 값과 비교합니다. 마찬가지로 일치하면 검색에 성공한 것이고 일치하지 않았다면 필요없는 부분을 잘라냅니다.
예시에서는 두 번만에 찾았지만 계속 진행한다면 마지막 1칸으로 나누었을 때도 찾지 못하면 검색 실패가 됩니다.
2. 이진 검색 구현
export const binarySearch = (arr, key) => {
//검색 부분의 맨 처음 head
let head = 0;
//검색 부분의 맨 뒤 tail
let tail = arr.length - 1;
//head === tail일때도 못찾았다면 검색 실패
while (head <= tail) {
//부분 배열의 중간 값을 지정하는 center 변수
let center = parseInt((head + tail) / 2);
//키와 중간 값이 일치하면 검색 성공
if (key === arr[center]) {
return console.log("검색 성공");
}
//키가 중간값보다 적으면 범위를 앞쪽 절반으로
else if (key < arr[center]) {
tail = center - 1;
}
//키가 중간값보다 크면 범위를 뒤쪽 절반으로
//else문으로 처리 가능
else if (key > arr[center]) {
head = center + 1;
}
}
return console.log("검색 실패");
};
import {binarySearch} from './study-code/search/binary-search.js';
const arr = [3, 9, 11, 15, 16, 21, 22, 26, 29];
console.log("검색 키: 26");
binarySearch(arr, 26);
console.log("검색 키: 4");
binarySearch(arr, 4);
https://github.com/Bam-j/algorithm-study/blob/main/study-code/search/binary-search.js
GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록
블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록. Contribute to Bam-j/algorithm-study development by creating an account on GitHub.
github.com
'Programming > 알고리즘' 카테고리의 다른 글
Boyer Moore 법 (0) | 2021.11.12 |
---|---|
브루트-포스 법 (0) | 2021.11.10 |
선형 검색 (0) | 2021.11.09 |
하노이 탑 (0) | 2021.11.08 |
재귀 알고리즘 - 유클리드 호제법 (0) | 2021.11.08 |
댓글