[알고리즘] 이진 탐색

이진탐색이란?

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

쉽게 말해 up&down 게임과 유사하다고 볼 수 있다.

 

시작점, 중간점, 끝점을 이용하여 탐색 범위를 설정하는데 탐색할 숫자가 중간점보다 크다면, 중간점보다 작은 수들은 배척시킴으로써 탐색 범위를 줄여나간다.

 

예제

 

찾고자 하는 수가 14일 때

- 중간점이 2개일 경우 둘 중 아무거나 해도 상관 없다.

1. 찾고자 하는 수와 중간점을 비교한다.

2. 찾고자 하는 수(14)가 중간점보다 작다면 중간점 아래를, 높다면 중간점 위의 숫자들을 제거해준다.

3. 찾고자 하는 수(14)가 중간점보다 크기 때문에 중간점보다 작은 수들을 제외하면 아래와 같이 남게 된다.

 

 

과정 반복

 

중간점이 찾고자 하는 숫자와 같다면 종료한다.

 

코드

반복문

def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2

    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      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, n-1)
if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

 

재귀 함수

def binary_search(array, target, start, end):
  if start > end:
  	return None
  # 중간값
  mid = (start + end) // 2
  # 리스트의 중간값이 탐색값이라면 인덱스 반환
  if array[mid] == target:
  	return mid
  # 리스트의 중간값이 탐색값보다 크다면 끝점을 중간값 -1 로 변경 후 재귀호출
  elif array[mid] > target:
  	return binary_search(array, target, start, mid - 1)
  # 리스트의 중간값이 탐색값보다 작다면 시작점을 중간값 + 1 로 변경 후 재귀호출  
  else:
  	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, n-1)
if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)