[이코테]이진 탐색

Coding Test 5

이코테 5

순차 탐색 vs 이진 탐색

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  (시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정)

---

이진 탐색

• 동작 예시
  [Step 0] 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시

  [Step 1] 시작점: 0, 중간점: 4, 끝점: 9

  [Step 2] 시작점: 0, 중간점: 1, 끝점: 3

  [Step 3] 시작점: 2, 중간점: 2, 끝점: 3

  시간 복잡도 O(logN)
공간 복잡도 O(N)

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)
if result == None :
  print("원소가 존재하지 않습니다")
else :
  print(result+1)

---

이진 탐색 라이브러리

• bisect_left(a, x) : 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a, x) : 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

ex) 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
  right_index = bisect_right(a, right_value)
  left_index = bisect_left(a, left_value)
  return right_index - left_index

a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

print(count_by_range(a, 4, 4)) #2
print(count_by_range(a, -1, 3)) #6

---

파라메트릭 서치

• 최적화 문제를 결정 문제(“예” 혹은 “아니오”)로 바꾸어 해결하는 기법
• 이진 탐색을 이용하여 해결

---

문제1-떡볶이 떡 만들기

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
19, 14, 10, 17cm인 떡이 있고 절단기 높이가 15cm이면 자른 후 떡의 길이는 15, 14, 10, 15cm가 된다. 잘린 떡은 4, 0, 0, 2cm이며 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값은?

입력예시
4 6
19 15 10 17

출력예시
15

💡이진탐색 판별 Tip
절단기의 높이는 0~10억
이렇게 큰 탐색 범위를 보면 이진 탐색 떠올리기

[Step 1] 시작점: 0, 끝점: 19, 중간점: 9

[Step 2] 시작점: 10, 끝점: 19, 중간점: 14

[Step 3] 시작점: 15, 끝점: 19, 중간점: 17

[Step 4] 시작점: 15, 끝점: 16, 중간점: 15

n, m = list(map(int, input().split()))
array = list(map(int, input().split()))

start = 0
end = max(array)

result = 0
while (start <= end):
  total = 0
  mid = (start+end)//2
  for x in array: #잘린 떡의 양 계산
    if x > mid:
      total += x - mid
  if total < m: #떡의 양이 부족할 때
    end = mid - 1
  else : #떡의 양이 충분할 때
    result = mid
    start = mid + 1

print(result)

---

문제2-정렬된 배열에서 특정 수의 개수 구하기

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요.
시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간초과

입력예시
7 2
1 1 2 2 2 2 3

출력예시
4

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
  right_index = bisect_right(a, right_value)
  left_index = bisect_left(a, left_value)
  return right_index - left_index

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

count = count_by_range(array, x, x)

if count == 0:
  print(-1)
else :
  print(count)