이진 탐색

  이진 탐색 전에 정렬 알고리즘에 대해서 공부하고 난 다음에 이진 탐색에 대해서 정리하고 싶었는데,  dreambooth 문제 해결하느라 정리해서 올리지 못했다. 이진탐색(Binary Search)란 정렬되어 있는 상태의 array에서 target을 찾는 알고리즘 문제이다. 처음과 끝 점을 설정하고, 예를 들어 start, end = 0, len(nums)-1 로 설정한 다음에 중간 위치의 index를 mid로 설정한다. target과 binary_search[mid] 값을 비교하여  start나 end 값을 이동하는 방식이다. 

binary_search 출처 : wikipedia

 

# 수도코드
function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

  이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만 아무리 큰 길이의 리스트라도 정렬되어 있다면 target을 찾는 확률은 이진 탐색이 반복될 수록  2배가 되는 장점이 있어 속도가 빠르다.  재귀적인 방식과 반복적인 방식으로 사용할 수 있으며 python에는 기본적으로 이진 검색 모듈이 bisect로 들어가 있기 때문에 더 깔끔하게 사용할 수 있다. 

 

 

# 이진 탐색 소스코드 구현(재귀함수)
def binary_search(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

  투 포인터 방식이나 이진 탐색방식 모두 시간 복잡도 O(log n)가지기 때문에 상황에 따라 적절한 방식을 사용하면 좋을 것이다. 이진 탐색은 정렬된 상태에서 사용하지만 투 포인터는 정렬되지 않은 경우에도 사용 가능하다고 한다. 투포인터에 대해서도 정리를 해야겠다.