.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
탐색
•
순차 탐색: 리스트 안에 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
•
이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 기법
◦
이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함
•
시간 복잡도: O(logN)
•
큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 함
동작방식 (재귀)
1.
정렬된 배열에서 중간 인덱스(mid)를 찾는다.
2.
찾으려는 값(target)과 중간 값(mid_val)을 비교한다.
3.
target이 mid_val보다 작으면 mid를 기준으로 왼쪽 부분 배열을 탐색한다.target이 mid_val보다 크면 mid를 기준으로 오른쪽 부분 배열을 탐색한다.
4.
탐색 범위를 반으로 줄인다.
5.
탐색 범위가 더 이상 없을 때까지 위 과정을 반복한다.
def binary_search(array, target, start, end): # array: 리스트, target: 찾고자 하는 값, start: 시작 인덱스, end: 끝 인덱스
if start > end: # 시작 인덱스가 끝 인덱스보다 크면 False 반환
return False
mid = start + end / 2 # 중간 인덱스
if array[mid] == target: # 중간 인덱스 값이 target과 같으면 mid 반환
return mid
elif array[mid] > target: # 중간 인덱스 값이 target보다 크면 왼쪽 부분 탐색
return binary_search(array, target, start, mid - 1) # 중간 인덱스 값이 target보다 크면 왼쪽 부분 탐색
else:
return binary_search(array, target, mid + 1, end) # 중간 인덱스 값이 target보다 작으면 오른쪽 부분 탐색
Python
복사
파이썬 이진 탐색 라이브러리 (bisect)
•
bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환 (literable, value)
•
bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환 (literable, value)
•
참고 : 값이 특정 범위에 속하는 데이터 개수 구할 때
◦
bisect_left결과와 bisect_left결과의 차이를 통해 할 수 있음
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(a)
print(bisect_left(a, x)) # 인덱스 반환
print(bisect_right(a, x)) # 인덱스 반환
Python
복사
파라메트릭 서치(Parametric Search)
•
파라메트릭 서치란 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법
◦
ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화문제
•
일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 통해 해결할 수 있음.
•
큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 함
