서론
두번째로 이번 글에서 다룰 검색 알고리즘은 이진검색 알고리즘이다. 사실 이것도 이전에 했던 내용과 비슷한 것이 있다. 하지만 복습한다 생각하고 함께 살펴보도록 하자.
본론
이진검색 알고리즘은 선형검색 알고리즘보다 한 층 더 향상된 알고리즘이다. 전체를 비교하지 않고 일부를 비교하기 때문에 더 효율적이지만, 정렬되지 않은 데이터에서는 사용할 수 없다. 꼭 정렬된 배열과 같은 정렬됨 + 선형의 데이터에서만 사용할 수 있는 알고리즘이다. 그 특징을 더 알아보자.
이진검색 알고리즘
- 정형화된 선형의 데이터에서 사용
- 최선 O(1), 최악 O(logn)의 시간 복잡도 (선형검색 알고리즘보다 향상되었다!)
- 정렬되지 않은 데이터에서는 사용불가
이진검색 알고리즘이란?
이진검색 알고리즘은 정렬된 데이터에서 내가 원하는 데이터를 알아내고자 할 때 사용할 수 있는 알고리즘이다. 먼저 데이터의 중심점을 찾아 반으로 나눈 뒤, 두 덩이로 나뉘어진 데이터의 앞쪽이나 뒷쪽을 비교해서 원하는 데이터가 해당하는 범위가 아닌 데이터는 버리고 해당하는 데이터만 가지고 다시 검색을 실시하는 알고리즘이다. 처음부터 모두 비교할 필요없이 전체를 반으로 나누고 그 중 범위에 맞는 덩어리만 가지고 다시 반으로 나누면서 비교한다. 때문에 선형 알고리즘으로는 몇 번이고 해야하는 반복을 획기적으로 줄일 수 있다.
줄글로만 쓰니 감이 잘 오지 않을것이다. 해당 알고리즘이 어떤 것인지 코드로 구현해보자.
function binarySearch(arr, val){
let start = 0;
let end = arr.length-1;
let middle = Math.floor((start + end) / 2);
while(arr[middle] !== val) {
if(val < arr[middle]){
end = middle - 1;
}else{
start = middle + 1;
}
middle = Math.floor((start + end) / 2);
}
return middle;
}이런식으로 구현이 된다. 이걸 보니 무언가 떠오르는게 있다. 예전에 풀었던 분할과 정복 알고리즘 문제들이다. 이진검색 알고리즘은 분할과 정복의 원리가 기반에 있는 알고리즘이다. 아래에 그때의 글들을 링크로 첨부하겠다. 분할과 정복 알고리즘까지 궁금하신 분들은 한 번 보시는 것도 좋을것 같다.
https://velog.io/@eprnfmfmfm/22일차Divide-and-Conquer
https://velog.io/@eprnfmfmfm/23일차-Divide-and-Ququer
참고
