14. 이진 탐색 : 문제 풀이 전략

이진 탐색은 내부의 데이터가 정렬되어 있어야만 상용할 수 있는 알고리즘이다.

이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다.

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정.

 

 

1. 시작점 끝점을 확인한 다음 둘 사이 중간점을 정한다. 중간점이 실수 일 때는 소수점 이하를 버린다.

2. 중간점과 찾으려는 데이터를 비교한다.

3. 중간점에 있는 데이터가 더 크다면 중간점 -1의 데이터를 끝점으로 옮긴다.

 

위 과정을 반복하면 시간복잡도 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 = list(map(int,input().split()))
array = list(map(int,input().split()))

result = binary_search(array, target, 0, n-1)
print(array)
print(result+1)

이진 탐색 코드는 꼭 외워보자. 다른 알고리즘과 같이 많이 사용한다.

탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근해보자.

처리해야할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야하는 알고리즘을 떠올려야 한다.

탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자.

 

이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하자

 

import sys

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

print(input_data)

연습 문제

 

전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다고 한다. 매장에 부품 M개 종류를 모두 확인해서 견적서를 작성하자.

 

import sys

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 = int(input())


input_data = sys.stdin.readline().rstrip()
store = list(map(int,input_data.split()))

M = int(input())

input_data = sys.stdin.readline().rstrip()
client = list(map(int,input_data.split()))

store.sort()
client.sort()

for i in range(M):
  if None == binary_search(store, client[i], 0, N -1):
    print("no", end= ' ')
  else:
    print("yes", end= ' ')

계수 정렬로 풀기

n = int(input())
array = [0]* 100001

for i in input().split():
  array[int(i)] = 1

m = int(input())

x= list(map(int, input().split()))

for i in x:
  if array[i] == 1:
    print("yes", end=' ')
  else :
    print("no", end=' ')