알고리즘 : 이진 탐색(Binary Search)

이진 탐색(Binary Search)란?

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

 

출처 : penjee

 

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

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

이진 탐색
- Divide : 리스트를 두 개의 서브 리스트로 나눔
- Conquer
  - 검색할 숫자(search) > 중간값이면 뒷부분의 서브 리스트에서 검색할 숫자를 찾음
  - 검색할 숫자(search) < 중간값이면 앞 부분의 서브 리스트에서 검색할 숫자를 찾음

코드로 만드는 방법은?

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

 

알고리즘 구현

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
#출력결과 [69, 65, 18, 71, 11, 10, 42, 68, 36, 89]

data_list.sort()
data_list
#출력결과 [10, 11, 18, 36, 42, 65, 68, 69, 71, 89]

binary_search(data_list, 66)
"""
출력
[10, 11, 18, 36, 42, 65, 68, 69, 71, 89]
[68, 69, 71, 89]
[68, 69]
[68]
False
"""