이진 탐색 (Binary Search)

이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.

잔재미코딩 소식 공유

좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다

● 직운영 온라인 강의 서비스 오픈

● 잔재미코딩 유투브 오픈 [구독해보기]

11. 탐색 알고리즘2: 이진 탐색 (Binary Search)¶

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

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

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

No description has been provided for this image

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

[저작자] by penjee.com 이미지 출처

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

분할 정복 알고리즘 (Divide and Conquer)
- Divide: 문제를 하나 또는 둘 이상으로 나눈다.
- Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.
이진 탐색
- Divide: 리스트를 두 개의 서브 리스트로 나눈다.
- Comquer
  - 검색할 숫자 (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 찾기
    - data_list의 중간값 < find_data 이라면
      - data_list의 중간부터 맨 끝까지에서 다시 find_data 찾기
    - 그렇지 않다면, data_list의 중간값은 find_data 인 경우로, return data_list 중간위치

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

자세히 알아보기 모든 강좌 보기

4. 알고리즘 구현¶

In [9]:

def binary_search (data, search):
    print (data)
    if len(data) == 1:
        if data[0] == search:
            return True
        else:
            return False
    if len(data) == 0:
        return False
        
    medium = len(data) // 2
    if search == data[medium]:
        return True
    if search > data[medium]:
        return binary_search(data[medium:], search)
    else:
        return binary_search(data[:medium], search)

리스트 데이터 정렬하기 (sort 함수)¶

In [10]:

import random 
data_list = random.sample(range(100), 11)
data_list.sort()

테스트¶

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

자세히 알아보기 모든 강좌 보기

In [11]:

binary_search(data_list, 50)

[1, 12, 29, 38, 50, 69, 73, 76, 86, 94, 97]
[1, 12, 29, 38, 50]
[29, 38, 50]
[38, 50]

Out[11]:

True

5. 알고리즘 분석¶

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

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

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

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