[이진탐색] 이진탐색 (2) 이진 탐색

이진탐색 : 반으로 쪼개면서 탐색하기

• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능
  
  • 데이터가 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
• 위치를 나타내는 변수 3가지 존재
  • 탐색하고자 하는 범위의 시작점, 끝점, 중간점
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾음
• 탐색 과정 예시 - [0, 2, 4, 6, 8, 10,12, 14, 16, 18]에서 4를 찾을 때
  1. 시작점 0, 끝점 9, 중간점 =  (0 + 9) // 2 = 4.5 인데 소수점 이하를 버려서 4 ➡️ 중간점인 4번 인덱스의 데이터인 8은 target인 4보다 큼 ➡️ 8보다 큰 데이터는 확인할 필요 없음. 끝점을 4번 인덱스의 이전인 3번 인덱스로 옮기기
  2. 시작점 0, 끝점 3, 중간점 = (0 + 3) // 2 = 1.5 인데 소수점 버려서 1 ➡️ 중간점인 1번 인덱스의 데이터인 2는 target인 4보다 작음 ➡️ 시작점을 1번 인덱스 이후인 2번 인덱스로 옮기기
  3. 시작점 2, 끝점 3, 중간점 = (2 + 3) // 2 = 2.5인데 소수점 버려서 2 ➡️ 중간점인 2번 인덱스의 데이터인 4와 target인 4가 같음 ➡️ 탐색 종료
• 이진 탐색은 한 단계를 거칠 때마다 확인하는 원소가 평균적으로 절반으로 감소함
  • ex) 32 ➡️ 16 ➡️ 8 ➡️ 4 ➡️ ...
  • 연산 횟수는 logN에 비례하며, 시간복잡도는 O(logN)
• 이진탐색 구현 방법은 2가지 - 재귀함수 이용, 반복문 이용

소스코드 1. 재귀함수를 이용하여 이진 탐색 구현

• mid = (start + end) // 2 에서 몫만 구하기 위해 몫 연산자인 //  사용
• // 대신 int()를 사용할 수 있음

# 이진 탐색 ver.재귀함수
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: # 중간점의 값보다 target이 작은 경우 왼쪽 확인
    return binary_search(array, target, start, mid - 1)
  else: # 중간점의 값보다 target이 큰 경우 오른쪽 확인
    return binary_search(array, target, mid + 1, end)

# n(원소 개수)과 target(찾고자 하는 문자열) 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, len(array) - 1)
if result == None:
  print("원소가 존재하지 않습니다")
else:
  print(result + 1)

 

소스코드 2. 반복문을 이용하여 이진탐색 구현

# 이진 탐색 ver.반복문
def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target: # target을 찾은 경우 중간점 인덱스 반환
      return mid
    elif array[mid] > target: # 중간점의 값보다 target이 작은 경우 왼쪽 확인
      end = mid - 1
    else: # 중간점의 값보다 target이 큰 경우 오른족 확인
      start = mid + 1
  return None

# n(원소 개수)과 target(찾고자 하는 문자열) 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, len(array) - 1)
if result == None:
  print("원소가 존재하지 않습니다")
else:
  print(result + 1)

코딩 테스트에서의 이진 탐색

• 코테에서 단골로 나오는 문제이니 외우는 것 권장
• 다른 알고리즘과 함께 사용되기도 함
• 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많음
  • 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근 권장
  • 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN) 속도를 내는 알고리즘 사용

빠르게 입력받기

• 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편
  • ex) 데이터의 개수가 1,000만개를 넘어가거나 탐색 범위의 크기가 1,000억 이상인 경우
• 입력 데이터의 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려서 시간 초과가 될 수 있음
• input() 함수 대신 sys 라이브러리의 readline() 함수 사용하기
  • 이때, rstrip() 함수를 꼭 호출하기
• 소스코드

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

print(input_data)