이진 탐색(Binary Search)

1. 이진 탐색(Binary Search)란?

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

 

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

이진탐색 vs 순차탐색

2. 분할 정복 알고리즘과 이진 탐색

• 분할 정복 알고리즘(Divide and Conquer)
  • Divide : 문제를 하나 또는 둘 이상으로 나눔
  • Conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결, 아니면 다시 나눔
• 이진 탐색
  • Divide : 리스트를 두 개의 서브 리스트로 나눔
  • Conquer
    • 검색할 숫자(search) > 중간값이면, 뒷 부분의 서브 리스트에서 검색
    • 검색할 숫자(search) < 중간값이면, 앞 부분의 서브 리스트에서 검색
• 이진 탐색을 분할 정복 알고리즘을 사용해서 쓴다면 재귀용법을 사용해서 구현 가능

 

3. 어떻게 코드로 만들까?

• 이진 탐색은 데이터가 정렬되어 있는 상태에서 진행
• 데이터가 [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 검색 찾기
      • find_data > data_list[중간값] 이면
        • data_list 중간값부터 맨 끝까지 다시 find_data 검색 찾기
      • 둘 다 아니면 data_list == find_data 인 경우로 return data_list[중간값]

 

4. 알고리즘 구현

def binary_search(data, search):
    if len(data) == 1 and search == data[0]:    #마지막에 찾은 데이터가 내가 찾은 숫자가 맞다면
        return True
    if len(data) == 1 and search != data[0]:    #내가 찾는 숫자가 데이터 리스트에 없다는 의미
        return False
    if len(data) == 0:
        return False
    
    #중간값
    medium = len(data)//2
    if search == data[medium]:
        return True
    else:
        if search > data[medium]:
            return binary_search(data[medium:], search)#중간값부터 맨 끝까지를 재귀함수로
        else:
            return binary_search(data[:medium], search)

import random

data_list = random.sample(range(100), 10)
data_list.sort()
data_list

binary_search(data_list, 18)

출력 : [18, 28, 33, 45, 64, 75, 86, 89, 94, 97] / True

 

5. 알고리즘 분석

• n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교선언을 k회 진행
  • n x 1/2 x 1/2 x 1/2 ... = 1
  • n x (1/2)^k = 1
  • n = 2^k = log2n = log22^k
  • log2n = k
• 빅 오 표기법으로는 k+1이 결국 최종 시간복잡도임(1이 되었을 때도, 비교연산을 한번 수행)
  결국 O(log2n + 1)이고 2와 1, 상수는 제거되므로 O(logn)임