본문 바로가기
Algorithm/알고리즘

[알고리즘] 이진 검색/탐색(Binary Search) 알고리즘 by javascript (ft. lower / upper bound)

by 썸머워즈 2022. 3. 26.
반응형

이진 검색/탐색 알고리즘 (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특정값보다 처음으로 큰 값이 나오는 위치를 반환해주는 알고리즘이다.

 

역시 이번에도 그림으로 살펴보자.

출처 :&nbsp;http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

 

 

특정 값을 찾아주는 이진탐색 알고리즘 특성 상 위 이미지 처럼 동일한 값이 여럿 존재할때 제대로 사용하기 힘들다.

그럴때 사용하는게 Lower Bound / Upper Bound 알고리즘이다.

 

특정 값 이상 범위만 찾고자할 때, 특정 값 미만 범위만 찾고자할 때, 특정값의 개수만 찾고자할 때 등 다양한 상황에서 활용이 가능하다.

 

입력에 따라 어떤식으로 반환하는지에 대한 예제 이미지가 더 있으니 한번 살펴보자.

출처 :&nbsp;http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

 

이제 코드로 하나씩 알아보자.

 

▷ 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으로-배우는-알고리즘-이분탐색

 

[Python 으로 배우는 알고리즘] 이분탐색(Binary Search)

어떤 배열에서 원하는 원소를 찾고자 한다면 어떻게 해야할까? 아마도 가장 간단한 방법은 배열의 첫 원소 부터 모든 원소를 검색하는 선형탐색일 것이다.

velog.io

반응형


댓글

TOP