새싹프로그래머의 이야기

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

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

오름차순으로 정렬된 배열에서 찾고자하는 element를 탐색하는 알고리즘 입니다.

데이터를 반으로 나눠가며 탐색을 진행합니다.

시간 복잡도는 O( log N ) 입니다.

 2. 구현 방법

• 배열에서 중간 값을 찾고자하는 target 값이랑 비교한다
• 중간 값 < target 이라면, 중간 값보다 오른쪽에 있는 배열로 범주를 좁혀 과정을 반복한다
• 중간 값 > target 이라면, 중간 값보다 왼쪽에 있는 배열로 범주를 좁혀 과정을 반복한다

3. 코드

백준 알고리즘 10815번을 기준으로 작성하였습니다.

myCard - 오름차순으로 정렬 되어 있는 배열

Binary Search - 반복문

def binarySearch(target):
    start = 0
    end = len(myCard) - 1

    while start <= end:
        mid = (start + end) // 2
        if myCard[mid] == target:
            return 1
        elif myCard[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return 0

Binary Search - 재귀

def binarySearch(target,start,end):
    mid = (start+end)//2

    if start > end:
        return 0
    if myCard[mid] == target:
        return 1
    elif myCard[mid] < target:
        start = mid + 1
    else:
        end = mid -1

    return binarySearch(target,start,end)