이분 탐색/이진 탐색 알고리즘 (binary search)

이분 탐색 알고리즘

이분 탐색 알고리즘이란, 정렬된 리스트에서 탐색 범위를 절반씩 줄여 나가면서 특정 값을 탐색하는 방법이다.

 

• 반드시 배열 내부의 값들이 '정렬'되어 있어야 함(단점)
• 속도가 빠르다(장점)
  • 탐색을 반복할 수록, 탐색 범위가 절반으로 줄어들기 때문
• 변수 3개를 이용하여 탐색 
  • start , mid , end

 

동작 방식

1. 배열의 중간 값(mid)를 가져온다.

2. 중간 값(mid)과, 탐색 값(key) 비교

  - mid = key : 종료 

  - mid < key : mid기준으로, 배열의 오른쪽 구간을 다시 탐색 (mid+1 index가 start원소로 변경)

  - mid > key :mid 기준으로, 배열의 왼쪽 구간을 다시 탐색 (mid-1 index가 end원소로 변경)

 

3. 종료

   - mid = key 일 때

   - 더 이상 탐색할 값이 존재하지 않을 때

 

 

 

이분탐색 방법

1. 반복문을 이용

 

def binary_search (arr, start,end,key):
  while start <= end :
    mid = (start + end) // 2;
    if arr[mid] == key: 
      return mid; 
    elif arr[mid] > key: 
      end = mid - 1      
    else: 
      start = mid + 1
  
  return None ; // 종료 조건 (start > end) 검색 실패.

n, key = list(map(int, input().split()))
arr = list(map(int, input().split()))

result = binary_search(array, key, 0, n - 1)
if result is None:
    print('원소가 존재 X')
else:
    print(result + 1)

2. 재귀 함수를 이용

함수 내부에서 자기 자신을 호출

 

def binary_search(arr, key, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    if arr[mid] == key:
        return mid
    
    elif arr[mid] > key:
        return binary_search(arr, key , start, mid - 1)
    
    else:
        return binary_search(arr, key, mid + 1, end)


n, key = list(map(int, input().split()))
arr = list(map(int, input().split()))

result = binary_search(arr, key, 0, n - 1)
if result is None:
    print('원소가 존재 X')
else:
    print(result + 1)

 

시간복잡도

• 시간복잡도는 O(logN)
  • log는 log₂ 를 의미
  • 단계마다 탐색 범위를 절반으로 줄이기 때문에, 위와 같은 시간복잡도를 가짐
  •  ex) 처음 데이터의 개수가 64개라면, 1단계를 거치면 약 32개의 데이터가 남고, 2단계에서 약 16개, 3단계에서 약 8개의 데이터만 남게 된다.

  

이분 탐색 관련 라이브러리

bisect

bisect_left(list, input)
리스트가 정렬 상태를 유지하면서, data가 list에 몇 번 인덱스로 들어갈지를 반환(가장 왼쪽)

bisect_right(list, input) --> 리스트가 정렬 상태를 유지하면서, data가 list에 몇 번 인덱스로 들어갈지를 반환(가장 오른쪽)

ex)

from bisect import bisect_left, bisect_right
lst = [1, 3, 4, 5]

print(bisect_left(lst, 3)) # 1출력
print(bisect_right(lst, 3)) # 2출력