[알고리즘][이진탐색] 이진탐색

이진탐색

이진 탐색(binary Search)는 찾으려는 데이터와 배열의 중간 위치에 있는 데이터를 반복적으로 비교해서 배열을 반복적으로 반으로 줄여나가는 알고리즘이다.

이진 탐색은 반드시 데이터가 정렬되어있는 상태에서만 사용할 수 있다.

이진 탐색에는 시작점, 끝점, 중간점 3개의 변수가 사용된다.

예를 들어 [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]의 배열이 주어지고 6의 위치를 찾아야 한다고 가정해보자.

배열의 길이가 10이기 때문에 중간 값인 5번째 데이터를 6과 비교한다. 5번째 요소는 10이고 (0부터 출발, 실제로는 6번째다) 이는 찾으려는 값인 6보다 크기 때문에 배열의 끝점을 4로 축소한다 (0부터 출발하기 때문에 5개가 남는다).

그 다음 남은 [0, 2, 4, 6, 8]에서 길이 5의 중간값인 2번째 데이터를 꺼낸다 (소수점 아래 자리는 없애고 몫만 사용한다).

이중 2번째 값은 4이며 이는 찾으려는 값인 6보다 작기 때문에 배열의 시작점을 3으로 이동한다.

이제 남은 배열 3번째에서 4번째 값인 [6, 8]이다. 이 때, 배열의 길이는 2이므로 중간값은 배열의 (3 + 4) // 2번째 값(3)이 된다.

배열의 3번째 값은 6이다. 이는 우리가 찾으려는 값과 일치하기 때문에 중 간값인 3을 반환한다.

이진 탐색은 한번의 반복으로 범위를 엄청나게 줄여주기 때문에, 값을 탐색해야 하는 범위가 매우 클 때 유용하다.

---

코드

def binary_search(array, target, start, end):
    if start > end:    # 남은 값이 없을 경우 종료
        return None
    mid = (start + mid) // 2
    if array[mid] == target:    # 중간값이 target이면 반환
        return mid
    elif array[mid] > target:   # 중간값이 target보다 크면 왼쪽 확인
        return binary_search(array, target, start, mid-1)
    else:						# 중간값이 target보다 작으면 오른쪽 확인
        return binary_search(array, target, mid+1, end)

A = list(map(int, input().split()))
N = int(input())

result = binary_search(A, N, 0, len(A) - 1)

if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(result)