정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 탐색 범위를 절반씩 줄여가며 찾는 Search 방법
예를 들어, [1 2 3 4 5 6]에서 4를 찾고자 한다면, 배열의 중간에 위차하는 3과 4를 비교한다.
4는 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들을 탐색할 필요가 없다. 따라서 3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도한다.
[4 5 6]이 남았다. 다시 중간값인 5와 찾고자 하는 4를 비교한다. 4는 5보다 작으므로, 5의 왼쪽에 있는 값들을 대상으로만 탐색을 다시 시도한다.
이제 [4]만 남았다. 4와 4를 비교하면 값이 일치하므로 탐색을 종료한다.
오름차순
으로 정렬되어야 한다.
def binary_search(target, data):
data.sort()
start = 0
end = len(data) - 1
while start <= end:
mid = (start + end) // 2
if data[mid] == target:
return mid # 함수를 끝내버린다.
elif data[mid] < target:
start = mid + 1
else:
end = mid -1
return None
# 재귀적 구현
def binary_search_recursion(target, start, end, data):
if start > end:
return None
mid = (start + end) // 2
if data[mid] == target:
return mid
elif data[mid] > target:
end = mid - 1
else:
start = mid + 1
return binary_search_recursion(target, start, end, data)
순차 탐색(linear search)는 Worst Case일 때 O(n)이라는 Time Complexity를 보인다.
그러나 이분 탐색은 탐색 대상을 절반씩 계속해서 줄여나가기 때문에 시간 복잡도가 O(logN)
이 된다.
** insert sort (삽입정렬), bubble sort, selection sort는 O(n^2)의 성능을 갖고 있다.
def solution(n, times):
answer = 0
left = 1
right = n * max(times)
while left <= right:
mid = (left + right) // 2
people = 0
for time in times:
people += mid//time
if people >= n:
answer = mid
right = mid - 1
else:
left = mid + 1
return answer
이분 탐색을 할 때는 ‘이분 탐색의 범위는 무엇으로 할지’ 와 ‘이분 탐색의 기준을 무엇으로 할지’ 을 잡아야한다.
right = mid - 1
)left = mid + 1
)
def solution(distance, rocks, n):
answer = 0
rocks.sort()
left = 0
right = distance
while left <= right:
mid = (left + right) // 2
removed = 0
current = 0
for rock in rocks:
diff = rock - current
if diff < mid:
removed += 1
else:
current = rock
if removed > n:
right = mid - 1
else:
answer = mid
left = mid + 1
return answer
이분 탐색(Binary Search) (수정 2019-02-15)