[알고리즘] 이진 탐색

1. 이진 탐색 (Binary Search) 란

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

 

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

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 찾기
      - data_list의 중간값 < find_data 이라면
        - data_list의 중간부터 맨 끝까지에서 다시 find_data 찾기
      - 그렇지 않다면, data_list의 중간값은 find_data 인 경우로, return data_list 중간위치

 

4. 알고리즘 구현

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)

5. 알고리즘 분석

- n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산을 k회 진행

- 빅오 표기법으로는 O(log2n+1)이고 상수는 삭제되므로 O(log n)

 

6. 실전 알고리즘(https://www.acmicpc.net/problem/1920)

왜 다음 코드가 좋지 않은 이유 - 실제로 다음과 같이 작성하면 시간 제한에 걸림

n = 5
n_list = [4,1,5,2,3]
m = 5
m_list = [1,3,7,9,5]

for item in m_list :
	if item in n_list :
    	print(1)
    else :
    	print(0)

 

시간복잡도 개선 코드 - 이진 탐색 알고리즘 기반 코드 개선

N = 5
N_list = [4, 1, 5, 2, 3]
M = 5
M_list = [1, 3, 7, 9, 5]

N_list.sort()
def binary_search(data, search) :
	if len(data)  == 0 :
    	return 0
    elif len(data) == 1 :
    	if data[0] == search:
        	return 1
        else:
        	return 0
    mid = len(data)//2
    if search == data[mid]:
    	return 1
   	else:
     if search > data[mid] :
    	return binary_search(data[mid:],search)
   	 else :
     	return binary_search(data[:mid],search)

for item in M_list :
	print( binary_search(N_list, item))

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))
N_list.sort()

def binary_search(value, start, end):
    if start > end:
        return False
    
    median = (start + end) // 2
    if N_list[median] > value:
        return binary_search(value, start, median - 1)
    elif N_list[median] < value:
        return binary_search(value, median + 1, end)
    else:
        return True
        
for item in M_list:
    if binary_search(item, 0, N - 1):
        print (1)
    else:
        print (0)