20250117 이것이 코딩 테스트다 챕터7(이진탐색)

순차 탐색

순차로 데이터 탐색.
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법.
데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인.
시간 복잡도 O(N)

이진 탐색

코딩 테스트에서 단골로 나오는 문제⭐️ 가급적 소스코드 외울 것.
이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 매우 넓은 편.
-> 데이터 개수가 1,000만개가 넘어가거나 탐색 범위의 크기가 1,000억 이상이면 이진 탐색 알고리즘을 의심해보자.
그리고 입력 데이터가 많기 때문에 import sys sys.stdin.readline().rstrip() 사용해서 시간 초과 피할 것.

배열 내부 데이터가 정렬되어 있어야만 사용할 수 있음.
따라서 데이터가 무작위일 때는 사용할 수 없지만 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음.
탐색 범위를 절반씩 좁혀가며 데이터 탐색.

탐색하고자 하는 범위의 시작점, 끝점, 중간점 3가지 변수 사용.
이 3가지를 통해 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터 찾음.
중간점이 실수일 때는 소수점 이하 버림. (몫만 사용. // 2, int()이용)

탐색 과정

1. 시작점과 끝점 확인한 다음 둘 사이의 중간점 정함.
   
2. 중간점의 데이터와 찾으려는 데이터 비교.
   2-1. 중간점의 데이터가 더 크면 중간점 이후의 값 확인할 필요 없음.
   2-2. 중간점의 데이터가 더 작으면 중간점 이전의 값 확인할 필요 없음.
   2-3. 중간점의 데이터와 동일하면 탐색 종료.
   
3. 중간점 데이터와 찾으려는 데이터가 동일하지 않을 시 시작점 or 끝점 이동.
   3-1. 중간점 데이터가 더 컸으면 중간점 이전 인덱스로 끝점 이동.
   3-2. 중간점 데이터가 더 작았으면 중간점 이후 인덱스로 시작점 이동.
   한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어듦. (퀵 정렬과 공통점)
   시간복잡도 O(logN)
   

구현 방법

재귀 함수 이용

def binary_search(array, target, start, end):
  # 값이 배열에 없는 경우. (end는 작아지고 start는 커지니까 값이 없을 경우 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)

  # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
  else:
    return binary_search(array, target, mid + 1, end)

반복문 이용

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

이진 탐색 트리

이진 탐색이 동작 할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조.
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
이진 탐색 트리 구현하는 문제는 출제 빈도가 낮음

탐색 과정

1. 부모 노드 방문.
2. 부모 노드와 찾는 원소값 비교. 2-1. 부모 노드값 보다 찾는 원소가 더 크면 오른쪽 노드 방문 2-2. 부모 노드값 보다 찾는 원소가 더 작으면 왼쪽 노드 방문 2-3. 동일하면 탐색 종료

---