https://medium.com/@imanshu822/binary-search-and-its-powerful-applications-39ae7d7bca69

이진탐색

• 정렬된 배열을 가정
• 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠름
• Time Complexity : O(logn)
• iteration, recursive 크게 두가지 구현 방법이 있음

linear search VS binary search

arr = [1, 3, 5, 7, 9, 11]
# goal: target 값이 있는 index를 찾는것

#1. Iteration method
def binary_search(arr, target):
    start, end = 0, len(arr) -1
    while start <= end:
      mid = (start + end) // 2
      if arr[mid] == target:
        return mid
      elif arr[mid] > target: # 왼쪽에 있다
        end = mid -1
      else: # arr[mid] < target # 오른쪽에 있다
        start = mid + 1
    return -1
print(binary_search(arr, 5))  # 2
print(binary_search(arr, 6))  # -1 (없음)


#2. Recursive method
def binary_search_recur(arr, target, start, end):
  if start>end:
    return -1
  mid = (start + end) //2
  if arr[mid] == target: 
    return mid
  elif arr[mid] > target : # 왼쪽에 있다
    return binary_search_recur(arr, target, start, mid-1)
  else: # 오른쪽에 있다
    return binary_search_recur(arr, target, mid+1, end)


print(binary_search_recur(arr, 5, 0, len(arr) - 1))  # 2
print(binary_search_recur(arr, 6, 0, len(arr) - 1))  # -1

중요 point

• 비교할때는 항상 target을 기준으로 생각.!
• 공간복잡도는 iteration 방법이 나음( O(1) > O(long n))