[알고리즘] 이분탐색 (binary search)

🕯️ 개념

정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 탐색 범위를 절반씩 줄여가며 찾는 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를 비교하면 값이 일치하므로 탐색을 종료한다.

• 정렬된 자료를 반으로 나누어 탐색하는 방법
• ⚠️  자료는 오름차순으로 정렬되어야 한다.
• 이진트리, 이진탐색은 코딩 인터뷰 단골 문제라고 한다 ^0^
• linear search는 순서대로 찾는 방식으로 정렬 방식이 상관 없는 반면, binary search는 반드시 정렬된 상태에서 시작해야 한다.
  • 그래야 로그 실행 시간을 보장한다.

 

---

👩‍💻 코드

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

이분 탐색을 할 때는 ‘이분 탐색의 범위는 무엇으로 할지’ 와 ‘이분 탐색의 기준을 무엇으로 할지’ 을 잡아야한다.

• 범위 : 심사를 하는데 총 걸리는 시간. 1분부터 가장 비효율적으로 심사를 받았을 때 걸리는 시간(분)으로 설정
• mid : 모든 심사관들에게 mid라는 시간이 주어진다. 모든 심사관들이 mid분 동안 심사한 사람의 수의 합(people)을 구해야 한다.
• 기준 : mid 동안 심사한 사람의 수(people)가
  1. 심사 받아야할 사람의 수(n)보다 많거나 같을 경우에는 시간이 충분했던 것이므로 주어진 시간을 줄이고 ( right = mid - 1)
  2. 심사 받아야할 사람의 수(n)보다 적은 경우에는 시간이 부족했던 것이므로 주어진 시간을 늘린다. (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

• 참고 : https://deok2kim.tistory.com/122

 

---

더 참고할 만한 자료

이분 탐색(Binary Search) (수정 2019-02-15)