[알고리즘] 이진탐색 + 문제풀이

순차탐색

• 리스트 안에 있는 특정 데이터를 찾기 위해 모든 데이터를 차례대로 확인하는 방법
• 정렬되지 않은 list에서 사용하며, 시간복잡도는 O(N)

 

이진탐색

• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터 탐색
• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능, 시간복잡도는 O(logN)
• 데이터의 개수나 값이 1,000만 단위 이상으로 넘어갈 때 사용하면 좋

+ 이진탐색트리

• 왼쪽 노드는 부모 노드보다 작고, 오른쪽 노드는 부모 노드보다 큼

1. 재귀함수를 이용한 이진탐색 코드

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)

  elif array[mid] < target:
    return binary_search(array, target, mid+1, end)
  
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)

 

2. 반복문을 이용한 이진탐색 코드

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

    elif array[mid] < target:
      start = mid+1

  return None

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)

 

3. 문제풀이 현황(기록용)

1	백준 10815번	실버 5	O	20230201
2	백준 10816번	실버 4	△	20230201