[Python] 이진탐색

개념

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
• 한번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점은 퀵 정렬과 비슷
• 단계마다 2로 나누는 것과 동일 - 시간복잡도 O(logN)
• 효율적으로 삽입 가능

구현

• 재귀

def binary_searcy(array, target, start, end):
	if start > end:
    	return None
    mid = (start+end) // 2
    if array[mid] == target:
    	return mid
    elif array[mid] > target:
    	return binary_search(array, target, start, mid-1)
    else:
    	return binary_search(array, target, mid+1, end)

• 반복

def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start+end) // 2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid -1
        else:
        	start = mid + 1
	return None

 

참고

이것이 취업을 위한 코딩테스트이다