이분탐색

1. 이진탐색(Binary Search) 이란.

• 이진 탐색 알고리즘(Binary Search Algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 입니다.
• 오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여, 찾고자 하는 Key값과 비교하는 방식으로 돌아가는 알고리즘 입니다.
• 정렬된 리스트에서만 사용할 수 있다는 단점이 존재합니다.
• 검색이 될때마다 선형탐색(Linear Search)와는 비교할 수 없게 빨라집니다.

2. 이진탐색(Binary Search)의 시간 복잡도

log2^n

3. bisect

파이썬에서 가장 자주 사용하는 이분탐색 라이브러리
bisect의 사전적 의미는 이등분(2등분)이다. 파이썬에서 bisect모듈을 활용하면 이분 탐색을 통해 정렬된 list에 'a'라는 값이 어디에 들어가면 되는지 index로 알려준다.

bisect()와 bisect_right()

bisect()

a=[1,3,5,7]이라는 정렬된 List가 있을 때, 정수 2는 어디에 넣을 수 있을까? 1과 3 사이에 넣을 수 있겠지. 그럼 이 때 bisect()함수는 그 위치의 index값인 1을 return해준다.

즉, bisect(a)의 return 값은 0~4이다. 만약 정수 0을 a에 넣고자 한다면 0을 return할 것이고, 정수 8을 a에 넣고자 한다면 4를 return해 줄 것이다.

질문 ? : 그럼 5를 넣고자 한다면 뭐라고 return해줄까? 즉, 정렬된 List에 넣고자 하는 값이 이미 List에 있을 때 고민이 생기는데 이 고민의 답을 2개로 나누어 준 것이 bisect_left()이다.

무슨말이냐면 b=[1,3,5,5,5,7]에 정수 5의 bisect()값은 5이다. 같은 값이 이미 List에 있다면 같은 값들의 가장 오른쪽 index 를 return해준다.

• bisect_left() : bisect()함수와 동일하나 위의 질문에 대한 나머지 대답을 해결해준다. 즉, b=[1,3,5,5,5,7]에 정수 5의 bisect_left()값은 2이다. bisect()와 반대로 같은 값이 이미 List에 있다면 같은 값들의 가장 왼쪽 index를 return해준다.
• bisect_right() : bisect()와 동일한 함수이다. 위의 질문과 같은 이유로 헷갈릴 수 있어서 bisect_right()라는 이름의 함수를 추가적으로 사용할 수 있게한 것 같다.