이진탐색_BinarySearch

이진탐색(BinarySearch)

• 이진탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start,end,mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정이다.

def binary_search(target,start,end):
	if start >= end:
		return 0
	mid = (start + end) // 2
	
	if target == mid:
		return 1
	elif target > mid:
		start = mid + 1
	else:
		end = mid -1
	return binary_search(target,start,end

• 시간 복잡도는 O(logN) 이다.