이진 탐색 핵심 설명 + bisect라이브러리(lowerbound) (중요)

RostoryT·2022년 6월 18일

Binary Search bisect lowerbound upper_bound 바이너리서치 이진탐색

Brave Python

목록 보기

5/7

용감한 파이썬-이진탐색 링크 : https://covenant.tistory.com/133

중요 포인트

데이터 범위가 10,000,000을 넘어가는 경우(천만 이상 초대량의 탐색 필요 시)
이진탐색은 기본적으로 "정렬"이 되어있는 상태!
그리고 Pivot을 사용한다!
주의사항 : 타겟을 제외한 모든 값은 index 넘버로 사용함을 주의하자!!
(중요) 활용 방법은 다음과 같음
- 나무/랜선/떡 자르기처럼 정해지지 않은 임의의 중앙값을 찾아나가야할 경우
- 다음 그림과 같이 제일 긴 녀석을 전체범위로 해서 바이너리서치 ㄱㄱ
- 또다른 활용 방법은 bisect라이브러리를 사용하는거
  - bisect 라이브러리는 위 문제랑 다르게, 배열에 딱 저장된 값들 중 딱 정해진 값을 찾아내는 문제에서 활용 가능

매우중요 포인트

: 이진탐색 시 n이 아니라 n-1을 넣어줘야한다!(인덱스 0부터라서)
이진탐색 while문 조건은 < 가 아니라 <= 를 해줘야한다!

이진탐색 수행하는 이유

수행(또는 탐색)할 범위가 엄청 넓거나 많은 경우,
그렇게 하지 말고 반토막내면서 텅~텅~ 진행
- https://velog.io/@taehyeon96/백준1654-랜선-자르기이진탐색

이진탐색 상세히 설명된 블로그(애니메이션 포함)

링크 : https://data-flower.tistory.com/99

Baseline Code of Binary Search

while문 사용 ver

# 타겟을 제외한 모든 값은 index 넘버로 사용함을 주의하자!!

def bin_search(array, target, start, end):
    while start <= end:
        pivot = (start + end) // 2
        
        if target == array[pivot]:
            return pivot
        # 찾지 못한 경우 index값을 당겨준다!!!
        elif target < array[pivot]:
            end = pivot-1
        elif target > array[pivot]:
            start = pivot+1
        
    return None  # (중요) 도출할 결과 없으면 이렇게!!! <-- DFS에서도 써먹어

n = 10
target = 7
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

result = bin_search(array, target, 0, n-1)

if result:
    print("Target's index num = ", result)
else:
    print("해당 원소가 없음")

재귀호출 ver

def binarySearch(array, value, low, high):
    if low > high:
        return False
    mid = (low+high) / 2
    if array[mid] > value:
        return binarySearch(array, value, low, mid-1)
    elif array[mid] < value:
        return binarySearch(array, value, mid+1, high)
    else:
        return mid

이진탐색의 장단점

장점
1. 정렬이 되어있어야만 가능하다
1. O(logN)이므로 매우 빠르다
2. 매우 큰 범위가 input으로 주어질 경우 이진탐색을 고려해라!
단점
1. 정렬되지 않았다면, 정렬하는데 시간이 오래걸린다

문제 링크 : https://covenant.tistory.com/133

파이썬에서 이진탐색을 라이브러리로 제공함

bisect 라이브러리

시간복잡도 : O(log n)

from bisect import bisect
from bisect import bisect_left, bisect_right

참고 링크 1 : https://programming119.tistory.com/196
참고 링크 2 : https://heytech.tistory.com/79

bisect_left(정렬된 배열, 찾을값) : 왼쪽 "인덱스"를 구하기

bisect_left()는 찾고자 하는 값의 lower_bound() "인덱스"를 구하는 함수!
bisect_right(정렬된 배열, 찾을값) : 오른쪽 "인덱스"를 구하기

이렇게 생각하는 방법이 있고
이렇게 생각하는 방법이 있겠다

예제 1

from bisect import bisect_left, bisect_right

nums = [0,1,2,3,4,5,6,7,8,9]
n = 5

print(bisect_left(nums, n))
print(bisect_right(nums, n))

'''
결과값
5
6
'''

예제 2

from bisect import bisect_left, bisect_right

nums = [4, 5, 5, 5, 5, 5, 5, 5, 5, 6]
n = 5

print(bisect_left(nums, n))
print(bisect_right(nums, n))


'''
결과값
1
9
'''