Binary Search_이진탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

---

코드

 

#1. recursive를 이용함
def binary_search(array, target, start, end):
	if start>end:
		return None
	mid = (start + end) // 2

	#찾으려는 target이 array의 중간에 있다면
	if target == array[mid]:
		return array[mid]
	#중간보다 작다면 -> 끝점을 중간 하나 전으로 옮긴다. 	
	elif target<array[mid]:
		return binary_search(array, target, start, mid-1)
	#중간보다 크다면 -> 시작점을 중간 다음으로 옮긴다.
	else:
		return binary_search(array, target, mid+1, end)


n, target = int(input().split())
array = list(map(int, input().split()))


result = binary_search(array, target, 0, n-1)

if result == None:
	print('존재하지 않습니다')
else:
	print(result+1) # index를 알려준다

 

#2. 반복문을 이용함
def binary_search(array, target, start, end):
	while start<=end:
		mid = (start+end)//2
	    if target == array[mid]:
		    return target

	    elif target < array[mid]:
	    	end = mid-1

	    else:
	    	start = mid+1

---

구현 방법

초기 상태: 찾으려는 수(9)와 정렬된 배열이 있다. 

1.

• start: 배열의 처음, 즉 인덱스 0  --> 이 경우는 0
• end: 배열의 끝, 즉 인덱스 arr.length()-1 --> 이 경우는 9
• mid = (start+end)/2 --> 이 경우는 (0+9)/2 == 4

• 찾으려는 수 9 는 arr[mid]인 15보다 작음을 확인할 수 있다.

2.

• 찾으려는 수가 중간의 값보다 작기 떄문에
• start: 아까와 같다 0
• end: mid보다 한 칸 왼쪽으로 간다. 즉, 1 작은 인덱스 3
• mid: (0+3)/2 == 1

• 찾으려는 수 9는 arr[mid]인 8보다 큼을 확인할 수 있다. 

3.

• 찾으려는 수가 중간의 값보다 크기 때문에 
• start: mid보다 한 칸 더 오른쪽으로 간다. 즉, 1 큰 인덱스 2
• end: 그대로 3으로 고정
• mid: (1+3)/2 == 2

• 찾으려는 수 9는 arr[mid]와 값이 같음을 알 수 있다.  

원하는 값을 찾았기 때문에 종료한다. 

---

시간 복잡도

 

크기가 N이라면, 한 번 비교를 할 때마다 범위가 1/2씩 줄어든다.

1번째 : N번, 2번째 : N/2번, 3번째: N/4번,  ...., 1번

따라서 

T(N) = T(N/2) + c #c는 비교 연산 등 여러 상수 시간의 연산들의 수행시간 

O(logN) 수행 시간을 가진다. 

 

 

---

출처

https://www.youtube.com/c/ChanSuShin

https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

https://blog.hexabrain.net/246

https://cjh5414.github.io/binary-search/