3. 이진탐색 알고리즘(binary_search)

이진 탐색(Binary_search)

 이진 탐색이란 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘이다.

입력 데이터가 많거나 탐색 범위의 크기가 매우 넓을 때 효과적으로 문제를 해결할 수 있다.

이진탐색 vs 순차탐색 (출처 : www.penjee.com)

단, 오름차순으로 정렬되어 있는 리스트가 있어야 하며, 데이터가 무작위로 정렬되어 있다면 사용할 수 없다.

 

정렬된 데이터에서만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목푯값을 찾을 확률은 두배가 되므로 속도가 빠르다는 장점이 있다.

 

이진 탐색의 동작 과정

 1. 시작 인덱스와 마지막 인덱스 사이의 중간 값을 중간 인덱스로 정한다.

   (이 때, 소수점 이하는 무시하고 중간 인덱스를 정한다.)

 

 2. 중간 인덱스에 해당하는 데이터와 현재 찾으려는 데이터(타겟)이 같은지 비교한다.

 

 3. 중간값이 찾으려는 데이터(타겟)보다 크다면 중간 인덱스 이후의 값은 확인하지 않고, 마지막 인덱스를 중간 인덱스로부터 한 칸 앞으로 옮긴다.

 반대로 중간 값이 찾으려는 데이터(타겟)보다 작다면, 시작 인덱스를 중간 인덱스로부터 한 칸 뒤로 옮긴다.

 

 4. 중간 인덱스의 값과 찾으려는 값이 같아질 때까지 2, 3번 과정을 반복한다.

 

이진 탐색의 시간 복잡도

 이진 탐색은 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 O(logN)이다.

확인하는 데이터의 개수가 절반씩 줄어드는 특징은 퀵 정렬과 동일하다.

 

이진 탐색과 단순 탐색의 비교

---

이진 탐색 코드 구현 방법

 1. 반복문을 활용한 이진 탐색 구현

def binary_search (arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2	#중간 인덱스는 시작인덱스+끝 인덱스를 2로 나눈 값
    
        # 중간 인덱스의 값이 타겟 데이터와 같은 경우 탐색 종료
        if arr[mid] == target:
            return mid
    
        # 중간 인덱스의 값이 타겟 데이터보다 큰 경우
        # 마지막 인덱스를 중간 인덱스의 한 칸 앞으로 이동
        elif arr[mid] > target:
            end = mid - 1
        
        # 중간 인덱스의 값이 타겟 데이터보다 작은 경우
        # 시작 인덱스를 중간 인덱스의 한 칸 뒤로 이동
        else:
            start = mid + 1
            
    return None

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = len(arr)
target = 4 #찾으려는 데이터의 값 = target
binary = binary_search(arr, target, 0, n-1)
print("찾으려는 데이터는 {}번째에 있습니다.".format(binary + 1))

 

 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)

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = len(arr)
target = 7 #찾으려는 데이터(타겟)
binary = binary_search(arr, target, 0, n-1)
print("찾으려는 데이터는 {}번째에 있습니다.".format(binary + 1))

 

 3. bisect 모듈 사용

 

 ㅇ bisect_left(a, x)

   - 정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾는다.

   - 만약 x가 이미 a에 있으면, 삽입 위치는 기존 항목 앞(왼쪽)이 된다.

 

 ㅇ bisect_right(a, x)

   - 정렬된 a에 x를 삽입할 위치를 리턴한다.

   - 만약 x가 이미 a에 있으면, 삽입 위치는 기존 항목 뒤(오른쪽)에 오는 삽입 위치를 반환한다.

 

import bisect
def binary_search(array=list(), target=int()):
    index = bisect.bisect_left(array, target)
    if index < len(array) and array[index] == target:
        return index
    return None

array=[-1, 0, 3, 5, 9, 12]
print(binary_search(array=array, target=9))

 

 ㅇ count_by_range(a, left_value, right_value)

   - 정렬된 리스트 a에서 left_value ≤ x ≤ right_value 인 x의 개수를 O(logN)으로 찾는다.

   - 몇번 등장하는지 확인하거나, 범위 내에 몇 개의 데이터가 포함되는지 확인할 때 사용하면 좋다.

from bisect import bisect_right, bisect_left

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

a = [1,1,2,3,4,1,10]
a.sort()
print(count_by_range(a,1,1))