[이진 탐색 알고리즘] 예제1 - 이진 탐색

[이코테] 예제1 - 이진 탐색

(한줄평) 이진 탐색 기초 문제로 재귀, 반복문 구현 방식 둘다 풀어보면 좋은 문제!

이 문제는 n개의 숫자에서 찾으려고 하는 값(target)이 있으면 해당 인덱스를 출력하는 문제다.

(풀이1) 재귀 함수로 구현

풀이 시간: 15분 이내

1) 문제 해결 아이디어

<동작 과정>

1. 타겟을 찾으면 인덱스를 리턴한다.

2. 타겟이 중간점 값보다 작으면 왼쪽 부분에 대해 이진 탐색 수행을 위해 끝점을 (mid - 1)로 넘겨 binary_search()를 리턴한다.

3. 타겟이 중간점 값보다 크면 오른쪽 부분에 대해 이진 탐색 수행을 위해 시작점을 (mid + 1)로 넘겨 binary_search()를 리턴한다.

 

2, 3번에서 binary_search()를 그냥 호출하는 것이 아니라 binary_serach()의 리턴 값을 리턴해주어야 한다!!

 

2) 소스코드

# 이진 탐색
def binary_search(array, target, start, end):
  # 시작점과 끝점이 엇갈리면 종료
  if start > end:  return None
  mid = (start + end) // 2  # 소수점은 버림

  # 1. 타겟이 중간점과 같다면 인덱스 리턴
  if target == array[mid]:  return mid
  # 2. 타겟이 중간점보다 작다면
  elif target < array[mid]:
    # mid 왼쪽 부분에 대해 이진 탐색 수행
    return binary_search(array, target, start, mid - 1)
  # 3. 타겟이 중간점보다 크다면
  else:
    # mid 오른쪽 부분에 대해 이진 탐색 수행
    return binary_search(array, target, mid + 1, end)

n, target = map(int, input().split())  # 원소 개수, 찾고자하는 값
array = list(map(int, input().split()))  # n개의 원소

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

(풀이2) 반복문으로 구현

풀이 시간: 10분 이내

1) 문제 해결 아이디어

<동작 과정>

1. 타겟을 찾으면 인덱스를 리턴한다.

2. 타겟이 중간점 값보다 작으면 왼쪽 부분에 대해 이진 탐색 수행을 위해 끝점을 (mid + 1)로 변경한다

3. 타겟이 중간점 값보다 크면 오른쪽 부분에 대해 이진 탐색 수행을 위해 시작점을 (mid + 1)로 변경한다.

 

2) 소스코드

def binary_search(array, target, start, end):
  while True:
    # 시작점과 끝점이 엇갈리면 종료
    if start > end:  return None
    mid = (start + end) // 2

    # 1. 타겟이 중간점과 같다면 인덱스 리턴
    if target == array[mid]:  return mid
    # 2. 타겟이 중간점보다 작다면 왼쪽 탐색
    elif target < array[mid]:
      end = mid - 1  # 끝 점을 (중간점 - 1)로 변경
    # 3. 타겟이 중간점보다 크다면 오른쪽 탐색
    else:
      start = mid + 1  # 끝 점을 (중간점 + 1)로 변경
    
n, target = map(int, input().split())  # 원소 개수, 찾고자하는 값
array = list(map(int, input().split()))  # n개의 원소

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