11. 이진 탐색 (Binary Search)¶

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

다음 문제를 먼저 생각해보자¶

이분 탐색의 이해 (순차 탐색과 비교하며 이해하기)¶

• [저작자] by penjee.com
• [이미지출처] https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

1. 리스트 중간에 있는 값 출력하기
2. 리스트 중간을 찾고, 리스트 처음부터 중간까지의 중간값을 출력해보기
import random 
data_size = random.randint(1, 100)
data_list = random.sample(range(100), data_size)

어떻게 코드로 만들까?¶

• 이진 탐색은 데이터가 정렬되있는 상태에서 진행
• 데이터가 [2, 3, 8, 12, 20] 일 때,
  • binary_search(data_list, find_data) 함수를 만들고
    • find_data는 찾는 숫자
    • data_list는 데이터 리스트
    • data_list의 중간값을 find_data와 비교해서
      • find_data < data_list의 중간값 이라면
        • 맨 앞부터 data_list의 중간까지 에서 다시 find_data 찾기
      • data_list의 중간값 < find_data 이라면
        • data_list의 중간부터 맨 끝까지에서 다시 find_data 찾기
      • 그렇지 않다면, data_list의 중간값은 find_data 인 경우로, return data_list 중간위치

코드를 뜯어보며 이해하기¶

알고리즘 분석¶

• n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산을 k회 진행
  • n X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ ... = 1
  • n X $\frac { 1 }{ 2 }^k$ = 1
  • n = $2^k$ = $log_2 n$ = $log_2 2^k$
  • $log_2 n$ = k
  • 빅 오 표기법으로는 k + 1 이 결국 최종 시간 복잡도임 (1이 되었을 때도, 비교연산을 한번 수행)
    • 결국 O($log_2 n$ + 1) 이고, 2와 1, 상수는 삭제 되므로, O($log n$)

import random 
data_size = random.randint(1, 100)
data_list = random.sample(range(100), data_size)

# 데이터 셋
import random 
data_list = random.sample(range(100000), 10000)

현재 시간 구하기¶
import datetime
print (datetime.datetime.now())