이진 탐색 (Binary Search)

순차 탐색 (Sequential Search)

: 리스트 안에 특정한 데이터를 찾기 위해, 앞에서부터 데이터를 하나씩 차례대로 확인하는 탐색방법 리스트레 해당하는 데이터가 존재하는지 탐색하는데 자주 사용된다.

시간복잡도 : 데이터가 N개일 때 N번의 비교연산이 필요하므로 O(N)

 

 이진 탐색 (Binary Search)

: 이진 탐색은 정렬되어있는 리스트내에서 탐색 범위를 반으로 쪼개가며 탐색하는 방법이다. 시작점, 끝점, 중간점 변수 3개를 이용해 탐색한다. 이진탐색을 구현하는 방법에는 2가지가 있다. 재귀함수를 사용하는 것과, 반복문을 사용하는 방법이다.

* 이진 탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다, 범위가 2000만을 넘는다면 이진 탐색으로 풀어보자. 처리해야 할 데이터의 개수가  1000만을 넘어가면 시간복잡도는 O(NlogN)을 가진 알고리즘을 이용해서 풀어야 한다!

시간복잡도 : 탐색마다 범위가 절반씩 줄어들기 때문에 연산횟수는 log2N에 비례한다. 때문에 시간복잡도는 O(logN)

 

def binary_search(array, target, start, end) :
    if start > end :
        return None
    mid = ( start +end ) // 2
    if array[mid] == target :
        return mid
    elif array[mid] > target :
        return binary_search(array, target, start, mid-1)
    else :
        return binary_search(array, target, mid+1, end)

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)