[알고리즘] 이진탐색 알고리즘과 파라메틱서치

이진탐색

• 정렬되어 있는 리스트에서 _탐색 범위를 절반씩 좁혀가며 데이터를 탐색_하는 방법 (로그시간의 시간복잡도)

  • 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다

    순차탐색

  • 리스트 안에 있는 특정한 _데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인_하는 방법

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례합니다

• 시간 복잡도는 _O(logN)_을 보장한다파이썬 이진 탐색 라이브러리

# 이진 탐색 소스코드 구현 (재귀 함수)
  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)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인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)

• bisect_left(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

• bisect_rigth(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽이할 가장 오른쪽 인덱스를 반환

  from bisect import bisect_left, bisect_right

from bisect import bisect_left, bisect_right