[이코테] 이진탐색

순차탐색: 기본적인 탐색 알고리즘

 

이진탐색 : 정렬된 리스트에서 탐색 범위 절반씩 좁혀가며 데이터 탐색

탐색범위: 시작점, 끝점, 중간점(소수점 이하 제거)

 

시간복잡도 : O(logN)

 

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

n, target = list(map(int, input().split()))

array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)