이진 탐색 (Binary Search)

### 이진 탐색 ###

: 데이터가 '정렬'된 상태에서 데이터를 반으로 나눠가며 특정 값을 찾는 방법

 

< 조건 >

: 정렬된 데이터 

 

 

< 시간 복잡도 >

  O(logn) 

 

 

< 풀이 >

: 시작점(start), 끝점(end), 중간점(mid)를 가지고 범위를 좁혀가며 값을 찾는다.

 

 

<예시 코드>

data = [1,2,3,4,5,6,7,8,9,10]
target = 2
start = 1
end = 10 

# 반복 사용
def binarySearch(start, end, target):
    while (start >= end):

        mid = (start+end) // 2 
        
        if (data[mid] == target):  
            return mid 

        elif (data[mid] < target):
            start = mid + 1 
        
        else:
            end = mid + 1

binarySearch(start, end, target)


#재귀 사용
def binarySearch2(start, end, target):
    if start > end:
        return None 
    
    mid = (start + end) // 2

    if (data[mid] == target):
        return mid 

    elif (data[mid] < target):
        return binarySearch2(mid + 1, end, target)

    else:
        return binarySearch2(start, mid - 1, target)