[ Python ] 이진 탐색 (binary search)

이진 탐색

정렬된 데이터에서 시작점, 끝점, 중간점을 정하여 , 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 알고리즘

시간 복잡도

• O(logN)

코드

# 재귀 함수로 구현한 이진 탐색
def binary_seacrh_recursive(nums,target,start,end):
  if start > end :
    return -1

  mid = (end+start)//2
  
  if nums[mid] == target:
    return mid
  elif nums[mid] > target:
    result = binary_seacrh_recursive(nums,target,0,mid-1)
  else:
    result = binary_seacrh_recursive(nums,target,mid+1,end)

  return result

# 반복문을 이용하여 구현한 이진 탐색
def binary_search(nums,target,start,end):

  while start <= end:
    mid = (start+end)//2
    if nums[mid] == target:
      return mid
    elif nums[mid] > target:
      end = mid-1
    else :
      start = mid+1

  return -1

# bisect 라이브러리를 이용한 이진 탐색
def py_binary_search(nums,target):
  # target의 왼쪽 인덱스 반환
  print(bisect_left(nums,target))
  # target의 오른쪽 인덱스 반환
  print(bisect_right(nums,target))