순차 탐색 &이진 탐색

순차탐색이란?

리스트에서 특정 데이터를 찾기 위해 앞에서부터 순차적으로 데이터를 확인하는 탐색 방법

 

이진탐색이란?

정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 하나씩 확인하는 방법

 - 시작점, 중간점, 끝점을 이용하여 탐색 범위를 설정

 - 시간복잡도 log(2)N

 

 

 

 

파이썬 라이브러리 bisect

from bisect import bisect_left, bisect_right

a = [1, 2, 3, 4, 4, 6, 7, 8]
x = 4
bl = bisect_left(a, x)  # 정렬을 유지하며 x를 삽입할 가장 왼쪽의 인덱스를 반환
br = bisect_right(a, x)  # 정렬을 유지하며 x를 삽입할 가장 오른쪽의 인덱스를 반환
print(bl)
print(br)

# 값이 특정 범위에 속하는 데이터 개수 구하기
def counter(arr, left_value, right_value):
    arr = sorted(arr)
    return bisect_right(arr, right_value) - bisect_left(arr, left_value)


print(counter(a, 3, 5))

파라메트릭 서치란?

- 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법

- 일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능

 

 

참고

https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5