이진 탐색(Python)

이진 탐색(Python)

 

 

오늘 배워 볼 내용은 이진탐색이다.

이진탐색은 탐색 범위를 절반씩 좁혀가면서 탐색한다는 특징이 있다. 또한 배열 내부의 데이터가 정렬 되어 있어야만 사용할 수 있는 알고리즘이니 참고하도록 하자.

 

핵심은 이렇다.

"찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교한다"

 

예시를 들어보자.

0

2

4

6

8

다음과 같은 배열이 있다. 2라는 순차는 몇번 인덱스에 있을까? 라는 문제가 나왔을 때 해결방법은 이렇다.

1. 재귀함수를 정의한다 (start, end,target, array가 존재하는)

2. start와 end를 2로 나누어 몫만 추린 값을 mid로 둔다.

3. mid값과 target을 중점적으로 비교해 같다면 return mid,  mid가 크다면 mid뒤에는 신경 안써도 되기 때문에 start는 그대로 두고 end값을 mid-1로 둔 뒤 재귀함수를 돌리면 된다. mid가 작을 경우에는 반대로 해준다.

4. 마지막 return 된 값에 +1을 해줘야 한다(인덱스는 0부터 시작하기 때문)

아래 소스코드를 통해 확인해보자.

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 = 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)

 

이진 탐색은 탐색 범위가 2,000만을 넘거가거나, 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 고려해야 할 알고리즘이다.

보통 이렇게 데이터의 값이 큰 경우에는 input()으로 입력을 받으면 속도가 느려서 오답 판정을 받을 수가 있다.

이와 같은 경우에는 sys 라이브러리의 readline() 함수를 이용하면 된다.

사용 방법은 이렇다.

 

import sys
input_data = sys.stdin.readline().rstrip()

print(input_data)

 

sys 라이브러리를 이용할 때는 뒤에 rstrip()을 꼭 호출하자. 엔터가 줄바꿈으로 입력되기 때문에 이를 지워줘야 한다.