파이썬과 컴퓨터 사이언스(알고리즘) - . 이진 탐색 (Binary Search)

11. 이진 탐색 (Binary Search)

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

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

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

프로그래밍 연습
임의 리스트가 있을 때,

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


In [ ]:
len(data_list) / 2
In [ ]:
len(data_list) // 2

어떻게 코드로 만들까?

  • 이진 탐색은 데이터가 정렬되있는 상태에서 진행
  • 데이터가 [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 중간위치

코드를 뜯어보며 이해하기

In [ ]:
import random 
data_list = random.sample(range(1000), 100)
In [ ]:
quick_sort(data_list)
In [ ]:
def binary_search(data_list, data):
    if len(data_list) == 1 and data_list[0] != data:
        return False
    elif len(data_list) == 1 and data_list[0] == data:
        return True
    
    medium = len(data_list) // 2
    
    if data > data_list[medium]:
        return binary_search(data_list[:medium], data)
    else:
        return binary_search(data_list[medium:], data)


In [ ]:
binary_search(data_list, 10)

알고리즘 분석

  • 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$)

프로그래밍 연습
임의 리스트가 다음과 같이 rand_data_list로 있을 때,

  • 입력: k 숫자가 주어지면, rand_data_list에 해당 데이터가 있는지를 알려주는 함수 작성하기 (퀵 정렬과 이분 탐색 각각 위의 자료를 참고해서 함수로 각각 작성해서 구현하기)
  • 출력: k 가 있으면 True, 없으면 False 를 리턴 </div>
    import random 
    data_size = random.randint(1, 100)
    data_list = random.sample(range(100), data_size)
    

협업 과제
다음 10000개의 데이터를 삽입 정렬, 병합 정렬, 퀵 정렬로 정렬해보고 각각 정렬 시간을 구하세요

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

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