🙌 이진탐색

🙌 순차 탐색(Sequential Search)

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

def sequential_search(n, target, array):
  for i in range(n):
    if array[i] == target:
      return i + 1

print(sequential_search(5, '나', ['가', '나', '다', '라', '마']))

🙌 이진 탐색 : 반으로 쪼개면서 탐색하기

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
• 시작점, 끝점, 중간점의 위치 변수를 사용하여 찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교해 원하는 데이터를 찾는 알고리즘
• 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근하기
• 이진 탐색의 시간 복잡도 : 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)
  elif array[mid] < target:
    return binary_search(array, target, mid+1, end)

• 이진 탐색 문제는 탐색 범위가 넓은 편이기에, 빠르게 입력받아야 시간초과를 피할 수있다.

import sys

input_data = sys.stdin.readline().rstrip()

print(input_data)