[알고리즘] 이분 탐색 / 이진 탐색 (binary search)

이분 탐색

- 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 떄 까지 탐색하는 알고리즘

- 조건 : 반드시 오름차순으로 정렬된 상태에서 시작해야 한다

 

Olog(N)

반복문과 재귀 두 가지 방법을 사용할 수 있다

 

target : 찾고자 하는 값

data : 오름차순으로 정렬된 list

start : data의 처음값 인덱스

end : data의 마지막 값 인덱스

mid : start, end 의 중간 인덱스

 

자료의 중갑 값(Mid) 차고자 하는 값인지 겁사

아니라며면 대소 관계를 비교하는 start, end 값 이동

동일 연산 반복 (재귀로 구현 가능)

 

자료의 중간 값이 찾고자 하는 값인지 비교

 mid값이 target과 다트라면 대소관계를 비교하여 탐색 범위를 좁히고, tqrget과 mid 값이 같을 때 까지 반복

1) target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다( 절반의 왼쪽)

2) target이 mid 값 보다 크면 start를 mid 오른쪽 값으로 바꿔준다( 절반의 오른쪽 탐색)

 

서치

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

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

    return None

 

 

 

이중 이분 탐색

- 같은 중복 데이터가 있을때 : 중복되는 데이터 개수 확인 가능

- low/upper 방식을 이중으로 사용

 

low 방식 : 제일 앞에 있는 부분에 위치에 있는 데이터 탐색

upper 방식 : 제일 마지막에 있는 데이터 확인 가능