이진 탐색(Binary Search)

이진 탐색 개념

---

정렬된 리스트에서 검색 범위를 줄여 나가며 검색 값을 찾는 알고리즘.

이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄어들기 때문에 시간 복잡도가 작다는 장점이 있다.

 

동작 방식

리스트의 중간 값과 비교하며 검색값을 찾는다.

반드시 리스트가 오름차순 정렬된 상태에서 시작해야 한다.

 

1. 배열의 중간 값을 가져온다.

2. 중간 값과 검색 값을 비교한다.

1. 중간 값이 검색 값과 같다면 종료
2. 중간 값보다 검색 값이 크다면 중간 값 기준 배열의 오른쪽 구간을 대상으로 탐색(low = mid + 1)
3. 중간 값보다 검색 값이 작다면 중간 값 기준 배열의 왼쪽 구간을 대상으로 탐색(high = mid - 1)

3. 값을 찾거나 더 이상 검색할 범위가 없을 때 종료한다.

 

구현

1. 반복문

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

    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target :
            return mid         #target 위치 반환
        elif data[mid] > target :
            high = mid - 1
        else:
            low = mid + 1           
    return -1  #리스트 안에 target이 존재하지 않을때

 

2. 재귀

def binary_search(target, start, end):
    if start > end:
        return -1    #범위를 넘어도 못찾으면 -1    
    mid = (start + end ) // 2    
    if data[mid] == target:
        return mid
    elif data[mid] > target:
        high = mid -1
    else:
        low = mid + 1
    return binary_search(target, start, end)     #줄어든 범위를 더 탐색

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