- 용감한 파이썬-이진탐색 링크 : https://covenant.tistory.com/133
중요 포인트
-
데이터 범위가 10,000,000을 넘어가는 경우(천만 이상 초대량의 탐색 필요 시)
-
이진탐색은 기본적으로 "정렬"이 되어있는 상태!
-
그리고 Pivot을 사용한다!
-
주의사항 : 타겟을 제외한 모든 값은 index 넘버로 사용함을 주의하자!!
-
(중요) 활용 방법은 다음과 같음
- 나무/랜선/떡 자르기처럼 정해지지 않은 임의의 중앙값을 찾아나가야할 경우
- 다음 그림과 같이 제일 긴 녀석을 전체범위로 해서 바이너리서치 ㄱㄱ
- 또다른 활용 방법은 bisect라이브러리를 사용하는거
- bisect 라이브러리는 위 문제랑 다르게, 배열에 딱 저장된 값들 중 딱 정해진 값을 찾아내는 문제에서 활용 가능
매우중요 포인트
- : 이진탐색 시 n이 아니라 n-1을 넣어줘야한다!(인덱스 0부터라서)
- 이진탐색 while문 조건은 < 가 아니라 <= 를 해줘야한다!
이진탐색 수행하는 이유
- 수행(또는 탐색)할 범위가 엄청 넓거나 많은 경우,
- 그렇게 하지 말고 반토막내면서 텅~텅~ 진행
이진탐색 상세히 설명된 블로그(애니메이션 포함)
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. 정렬이 되어있어야만 가능하다- O(logN)이므로 매우 빠르다
- 매우 큰 범위가 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
'''bisect 라이브러리 예제
Do My Best