[알고리즘] 5. 이진탐색

1. 이진탐색 Binary Search

1. 완전탐색인 선형탐색보다 효율적이다.

2. 이미 정렬이 되어있다는 가정하에 탐색이 필요없는 절반범위를 제외 및 탐색을 하는 것을 반복한다.
   → 탐색 전에 반드시 정렬되어 있어야 함!
   → 살펴보는 범위를 절반씩 줄여가며 탐색

   ※ 시간복잡도
   → 정렬 O(NlogN) + 이진탐색 O(logN) = O(NlogN)
   → 이진탐색 O(logN) = O(logN) : 미리 정렬이 되어있는 경우

   ※ 선형탐색 O(N)을 그냥하면 되지않나?
   → 탐색을 하는 과정이 1번이면 선형탐색이 유리
   → 탐색을 N번 한다? : 선형탐색은 O(N^2), 이진탐색은 O(NlogN)
   → 탐색을 여러번 할 경우 이진탐색이 유리!

1) 이진탐색 - 라이브러리

   ### bisect_left/right
   
   from bisect import bisect_left, bisect_right
   
   v = (0, 1, 3, 3, 6, 6, 6, 7, 8, 8, 9)
   three = bisect_right(v, 3) - bisect_left(v, 3)
   four = bisect_right(v, 4) - bisect_left(v, 4)
   six = bisect_right(v, 6) - bisect_left(v, 6)
   print(f'number of 3: {three}') # 2
   print(f'number of 4: {four}') # 0
   print(f'number of 6: {six}') # 3

2. 파라메트릭 서치

1. 최적화 문제를 결정 문제로 바꾸어서 이진탐색으로 푸는 방법
   → 최적화문제: 문제상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제
   → 결정 문제: 예/아니오

   ※ 이진 탐색을 하면서 상황의 조건이 바뀌는 경계값을 찾는다.

   • 매개변수 Parameter가 주어진면 true or false가 결정되어야 한다.
   • 가능한 해의 영역이 연속적이어야 한다.
   • 범위를 반씩 줄여가면서 가운데 값이 true 인지 false 인지 구한다.
   • 이진탐색과 똑같은 원리