이진 검색/탐색 알고리즘 (binary search algorithm)은
오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 절차를 지닌다.
처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 이러한 검색 원리로 원하는 값이 나올 때까지 반복하는 알고리즘이다.
이진 탐색 알고리즘 원리는 아래 그림을 살펴보면 좀 더 이해가 쉬울것이다.
검색 원리상 위에서 설명했지만 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목푯값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.
그렇다 보니 아무래도 선형 탐색의 시간 복잡도(O(N)) 보다는 이진 탐색의 시간 복잡도(O(logN))이 더 빠를 수밖에 없다.
이제 개념을 어느정도 익혔으면 코드를 통해 접해보자.
▷ 이진 탐색 알고리즘 구현 by javascript
const binarySearch = (arr, target) => {
let left = 0;
let right = arr.length - 1;
while(left <= right){
const mid = Math.floor((left + right) / 2);
if(arr[mid] === target) return mid;
else if(arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}코드가 그렇게 어렵지는 않은데, 위에 첨부된 이미지를 그대로 구현하면 이렇게 된다.
중앙 값(mid)를 구하고 값을 비교 한 뒤, left 나 right를 이동 그리고 다시 반복 하는 형식의 코드이다.
당연히 찾는 값이 없다면 -1을 반환한다.
추가적으로 이진탐색 알고리즘에는 Lower Bound 와 Upper Bound 라는 변형된 알고리즘이 존재하는데,
Lower Bound 는 특정값보다 처음으로 같거나 큰 값이 나오는 위치를 반환해주는 알고리즘이며
Upper Bound 는 특정값보다 처음으로 큰 값이 나오는 위치를 반환해주는 알고리즘이다.
역시 이번에도 그림으로 살펴보자.
특정 값을 찾아주는 이진탐색 알고리즘 특성 상 위 이미지 처럼 동일한 값이 여럿 존재할때 제대로 사용하기 힘들다.
그럴때 사용하는게 Lower Bound / Upper Bound 알고리즘이다.
특정 값 이상 범위만 찾고자할 때, 특정 값 미만 범위만 찾고자할 때, 특정값의 개수만 찾고자할 때 등 다양한 상황에서 활용이 가능하다.
입력에 따라 어떤식으로 반환하는지에 대한 예제 이미지가 더 있으니 한번 살펴보자.
이제 코드로 하나씩 알아보자.
▷ Lower Bound 알고리즘 구현 by javascript
const lowerBound = (arr, target) => {
let left = 0;
let right = arr.length;
while(left < right){
const mid = Math.floor((left + right) / 2);
if(arr[mid] >= target) right = mid;
else left = mid + 1;
}
return left;
}
조건에 맞게 좌우를 좁혀가며 탐색하는 형식이다.
마지막 값에 return을 left로 해주었는데, 이는 right를 반환해도 딱히 상관은없다 결국 둘이 한곳에서 만나기 때문이다.
여기서 lower bound 와 upper bound 둘다 유의해야할 점은 모든 데이터가 target보다 작을 경우 데이터 범위 밖의 값을 리턴해야 하기 때문에 일반적인 이진탐색과 달리 right = arr.length 로 지정해 준 것이다. (일반적인 이진탐색은 right = arr.length - 1 을 사용한다.)
▷ Upper Bound 알고리즘 구현 by javascript
const upperBound = (arr, target) => {
let left = 0;
let right = arr.length;
while(left < right){
const mid = Math.floor((left + right) / 2);
if(arr[mid] <= target) left = mid + 1;
else right = mid;
}
return right;
}
Upper Bound 역시 Lower Bound와 마찬가지로 좌우를 좁혀가며 탐색하고,
마지막은 left 나 right 무엇을 반환해도 상관없다.
중간 if문 부분만 바뀌고 나머지는 Lower Bound와 동일한 로직을 수행한다.
참고 : 위키백과 - 이진 검색 알고리즘
이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전
이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고
ko.wikipedia.org
[Python 으로 배우는 알고리즘] 이분탐색(Binary Search)
어떤 배열에서 원하는 원소를 찾고자 한다면 어떻게 해야할까? 아마도 가장 간단한 방법은 배열의 첫 원소 부터 모든 원소를 검색하는 선형탐색일 것이다.
velog.io
댓글