[샛길공부] 이진탐색(이분탐색) (feat. 이코테 유튜브강의)

백준 문제를 풀다가 또 새로운 단어를 마주치면서 시작한 공부

문제 풀기는 아래 참고 👇👇👇

https://coding-nurse.tistory.com/40?category=975166 

---

* 강의 채널 : 동빈나

* 강의 이름 : (이코테 2021 강의 몰아보기) 5. 이진탐색

* 강의 링크 : https://youtu.be/94RC-DsGMLo

 

---

 🎀 이진 탐색

*이진 탐색 : 정렬된 리스트에서 탐색범위를 절반씩 좁혀가며 데이터 탐색

 - 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 절반씩 좁혀가기

cf) 순차 탐색 : 리스트 안 앞에서부터 데이터를 하나씩 확인 탐색

 

*이진탐색 시 중간점이 소수로 나온다면 소수점 이하 제거한다.

*시작과 끝점을 움직이면서 반절씩 나눠주기

 

*재귀함수를 이용한 이진탐색 (클릭하면 github 연결 👉)▶

*반복문을 이용한 이진탐색 (클릭하면 github 연결 👉)▶

---

 🎀 파이썬 이진 탐색 라이브러리

* bisect_left ( a, x ): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

* bisect_right ( a, x ): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

* bisec_rigtht 값에서 bisec_left 값을 빼서 특정 범위 안에 속하는 데이터 개수를 구하는데 유용하다.

<예제>

from bisect import bisect_left, bisect_right
 
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_value
 
a = [1,2,3,3,3,3,4,4,8,9]
 
#값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))
 
 
#값이[-1,3]범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))

---

 🎀 파라메트릭 서치(Parametric Search)

* 파라메트릭 서치 : 최적화 문제를 결정할때 (Y / N)로 바꾸어 해결하는 기법

 중간점이 값은 시간이 지날수록 최적화 된 값이 됨. 중간점 값을 기록하여 원하는 값 찾기

 - ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

 

---

 

🧐공부 한줄 평 : 복잡하긴 하지만 시간초과를 보지않기 위해선 노력해야지!