[이코테 7-2, 7-3] 이진탐색

재귀 함수로 구현한 이진탐색

 

# 이진 탐색 코드 구현(재귀 함수)
def binary_search(array, target, start, end):
  if start > end:
    return None
  mid = (start + end) //2
  # 중간점의 값과 target 값이 같은 경우 인덱스 반환
  if array[mid] == target:
    return mid
  # 중간 점의 값보다 target 값이 작은 경우 중간점의 인쪽 확인
  elif array[mid] > target:
    return binary_search(array, target, start,mid-1)
  # 중간점의 값보다 찾고자 하는 값이 큰 경우 중간점의 오른쪽 확인
  else:
    return binary_search(array, target, mid+1, end)

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

# 이진탐색 수행결과 출력
result = binary_search(array, target, 0, n-1)
# 0: start의 인덱스, n-1: end의 인덱스
if result == None:
  print("원소가 존재하지 않음")
else:
  print(result+1)
  # 인덱스는 0부터 시작하기 때문에 1을 더해야 n번째 원소가 된다

 

 

반복문으로 구현한 이진탐색

 

# 이진 탐색 코드 구현(재귀 함수)
def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) //2
    # 중간점의 값과 target 값이 같은 경우 인덱스 반환
    if array[mid] == target:
      return mid
    # 중간 점의 값보다 target 값이 작은 경우 중간점의 인쪽 확인
    elif array[mid] > target:
     end = mid -1
  # 중간점의 값보다 찾고자 하는 값이 큰 경우 중간점의 오른쪽 확인
  else:
    start = mid +1

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

# 이진탐색 수행결과 출력
result = binary_search(array, target, 0, n-1)
# 0: start의 인덱스, n-1: end의 인덱스
if result == None:
  print("원소가 존재하지 않음")
else:
  print(result+1)
  # 인덱스는 0부터 시작하기 때문에 1을 더해야 n번째 원소가 된다

 

 

개인적으로는 반복문으로 구현한것이 더 직관적으로 느껴진다. 그래도 둘 다 구현할 수 있도록 익혀두자.