[알고리즘] #5_2 이진 탐색

** 대표적인 탐색 알고리즘

- 순차 탐색, 해시, 이진 탐색 트리, 이진 탐색, ...

 

 

 

** 이진 탐색(Binary Search)

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

 

클릭시 출처 이동

 

 

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

• 분할 정복 알고리즘 (Divide and Conquer)
  • Divide: 문제를 하나 또는 둘 이상으로 나눈다.
  • Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.

 

• 이진 탐색
  • Divide: 리스트를 두 개의 서브 리스트로 나눈다.
  • Comquer
    • 검색할 숫자 (search) > 중간값 이면, 뒷부분의 서브 리스트에서 검색할 숫자를 찾는다.
    • 검색할 숫자 (search) < 중간값 이면, 앞부분의 서브 리스트에서 검색할 숫자를 찾는다.

 

 

 

** 구현

def binary_search(data, search):
    print (data)
    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+1:], search)
        else:
            return binary_search(data[:medium], search)

 

# 확인

import random
data_list = random.sample(range(100), 10)
data_list.sort() # 원본 리스트 정렬

 

binary_search(data_list, 66)

 

 

 

** 알고리즘 분석

• 길이가 n인 리스트를 매번 2로 나누어 길이가 1이 될 때까지 비교연산을 k회 진행
  • n * (1/2)^k = 1
  • n = 2^k, logn = k
  • 따라서 시간 복잡도는 O(logn)

 

 

 

** 프로그래밍 연습

다음 10000개의 데이터를 삽입 정렬, 퀵 정렬로 정렬하는 함수를 각각 만들어보고, 각각의 정렬 시간을 출력하기

---

# 데이터 셋

import random

data_list = random.sample(range(100000), 10000)

 

# 현재 시간 구하기

import datetime

print (datetime.datetime.now())

 

- 코드 작성 부분

# 함수

def insertion_sort(data):
    for i in range(1, len(data)):
        for j in range(i-1, -1, -1):
            if data[j] < data[j-1]:
                data[j], data[j-1] = data[j-1], data[j]
            else:
                break
    return data

 

def quick_sort(data):
    if len(data) <= 1: return data
    
    pivot = data[0]
    left = [item for item in data[1:] if item < pivot]
    right = [item for item in data[1:] if pivot <= item]
    
    return quick_sort(left) + [pivot] + quick_sort(right)

 

# 확인

import random 
data_list = random.sample(range(100000), 1000) # 파이썬은 재귀 호출을 최대 1000번만 할 수 있음

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

# 실행 시간 계산: ms 단위
# 삽입 정렬
start_time = datetime.datetime.now().microsecond
insertion_sort(data_list)
finish_time = datetime.datetime.now().microsecond

print(finish_time - start_time)

# 퀵 정렬
start_time = datetime.datetime.now().microsecond
quick_sort(data_list)
finish_time = datetime.datetime.now().microsecond

print(finish_time - start_time)

 

 

- 결과

ex) 삽입 정렬: 67156 / 퀵 정렬: 57410

---