이진탐색(Binary Search)이란?
반으로 쪼개면서 탐색하기
-
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
-
탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징
-
위치를 나타내는 변수 3개를 사용
: 탐색하고자 하는 범위의 시작점, 끝점, 중간점 -
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색의 과정
동작 방식
- 배열의 중간 값을 가져온다.
- 중간 값과 검색 값을 비교
- 중간 값이 검색 값과 같다면 종료. (mid = key)
- 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색(mid < key)
- 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색 (mid > key)
- 값을 찾거나 간격이 비어있을 때까지 반복
♦ 종료 조건
- 검색을 성공할 경우
- 리스트에서 검색할 값과 같은 요소를 발견한 경우 ⇨ arr [mid] == key
- 검색을 실패한 경우
- 더 이상 검색할 범위가 없을 경우 ⇨ start > end
시간 복잡도
🕰 O(logN)
운이 좋으면 찾고자 하는 값이 중간값과 동일해서 탐색이 끝나지만 최악의 경우 남은 데이터가 하나가 될 때까지 탐색을 반복한다.
이진 탐색은 한번의 탐색마다 탐색 범위가 절반으로 줄어드는 특징으로 인해 O(logN) 의 시간 복잡도를 '보장' 한다.
구현 방법 (2가지)
- 재귀함수 이용
def binary_search(arr, target, start, end):
if start > end:
# 원소가 존재하지 않는 경우
return None
mid = (start+end)//2
# 찾은 경우 중간점 인덱스 반환
if arr[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif arr[mid] > target:
return binary_search(arr, target, start, mid-1)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
return binary_search(arr, target, mid+1, end)- 반복문 이용
def binary_search(arr, target, start, end):
while start <= end:
mid = (start+end)//2
# 찾은 경우 중간점 인덱스 반환
if arr[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif arr[mid] > target:
end = mid-1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid+1
return None💡 코딩테스트의 이진탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다.
- 탐색 범위가 2,000만을 넘어가면
- 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상
➜ 이진 탐색으로 문제에 접근해보기!
bisect 라이브러리 [Python]
- 파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리 제공
- '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용됨
대표 메소드
- bisect_left()
- 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메소드 - bisect_right()
- 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메소드
코드
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 4, 4, 8]
x = 4
print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 6
print(bisect_right(a, x) - bisect_left(a, x)) # 4➜ 정렬된 리스트에서 특정 범위에 속하는 원소의 개수를 구하는데 효과적이다.
(right - left 이용)
💻🐯