[Algorithm][Python] 이진탐색 (Binary Search)

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

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

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

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

• 보편적으로 Sequential 보다 빠르게 찾을 수 있다.
• 한번의 탐색으로 찾아야 할 범위가 1/2씩 줄어들기 때문

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

• 분할 정복 알고리즘 (Divide and Conquer)

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

• 이진탐색

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

3. 알고리즘 구현

def binary_search(data_list, search):
	if len(data_list) == 1 and data_list[0] == search:
		return true
	if len(data_list) == 1 and data_list[0] != search:
		return False
	if len(data_list) == 0:
		return False

	medium = int(len(data) //2 )
	if search == data_list[medium]:
		return True
	if search > data_list[medium]:
		return binary_search(data_list[medium+1:], search)
	else:
		return binary_search(data_list[:medium], search)

4. 알고리즘 분석

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