이진 탐색 알고리즘

이진탐색

• 정의 : 정렬 되어있는 리스트 에서 탐색 범위를 반으로 줄여가며 데이터를 탐색하는 방법.

def binay_search(arr,target,start,end) :
  # arr = 정렬된 해당 배열 , target = 목표 데이터 , start= 시작점, end = 끝점 

  if start > end:
    #탐색 범위에 데이터가 없다는 뜻
    return None
  mid = (start + end) // 2

  if arr[mid] == target :
    #찾고자 하는 값의 인덱스
    return mid
  elif target > arr[mid]:
    return binay_search(arr,target,mid+1,end)
  else:
    return binay_search(arr,target,start,mid-1)

• 주로 사용되는 유형
  • 파라메트릭 서치 : 최적화 문제를 여러번의 결정 문제 (예, 아니오)로 바꾸어 해결하는 기법.
  • 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
  • 탐색 범위가 크고 찾고자하는 값의 범위를 특정할 수 있는 경우.
  • 예시
    • 떡 자르기
    • 징검다리
    • 입국심사