[알고리즘] 이진탐색

공부 : 동빈나 유튜브 ( https://youtu.be/94RC-DsGMLo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC )

 

 

이진탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색
- 시작점, 끝점, 중간점
- 정렬되어 있어야 가능
- 단계마다 탐색 볌위를 2로 나누는 것과 동일 -- O(logN)

- 이진탐색은 재귀함수 또는 반복문을 통해 풀 수 있음

 

#재귀함수버전
def binarySearch(array, target, start, end):
    if target < array[start]: # start > end로 멈출수도 있음
        return None
    mid = (end+start)//2
    if array[mid] == target:
        return mid
    elif array[mid] < target:
        return binarySearch(array, target, mid + 1, end)
    elif array[mid] > target:
        return binarySearch(array, target, start, mid - 1)



n, target = list(map(int, input().split()))
numList = list(map(int, input().split()))
a = binarySearch(numList, target, 0, n-1)
if a != None:
  print(a-1)
else:
  print(a)

 

파이썬 이진 탐색 라이브러리
- bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
- bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) #출력값 : 2
print(bisect_right(a, x)) #출력값 : 4

파라메트릭 서치 (Parametric Search)
: 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법
--> 일반적으로 코딩 테스트에서 파라메트릭 서치문제는 이진탐색을 이용하여 해결 가능

 

백준 - 이진탐색 문제

 

10815번_숫자카드.py

1920번_수찾기.py

10816_숫자카드2.py

 

연습 코드 : https://github.com/mingxoxo/Algorithm/tree/master/study/이진탐색

GitHub - mingxoxo/Algorithm: 알고리즘