이진 탐색

(이코테 2021 강의 몰아보기) 5. 이진 탐색

---

이진 탐색 알고리즘

• 순차 탐색 : 리스트 안에 있는 특정하나 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

---

이진 탐색 동작 예시

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

• [Step 1] start : 0, end : 9, mid : 4 (소수점 이하 제거) → index!

• [Step 2] start : 0, end : 3, mid : 1 (소수점 이하 제거)
  mid가 target보다 크면 end = mid - 1

• [Step 3] start : 2, end : 3, mid : 2 (소수점 이하 제거)
  mid가 target보다 작으면 start = mid + 1

이진 탐색의 시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 $log_2 N$에 비례한다.

if문 좀 대신 써줘~~~

import sys

n, m = map(int, sys.stdin.readline().split())

powerList = []
nameList = []

# power와 name 따로 저장
for _ in range(n):
    name, power = sys.stdin.readline().split()
    power = int(power)
    if powerList and powerList[-1] == power: # 비내림차순이므로 index -1로 중복 검사
        continue
    else:
        powerList.append(power)
        nameList.append(name)

# 이진 탐색
for _ in range(m):
    p = int(sys.stdin.readline())
    start, end = 0, len(powerList) - 1
    while start <= end:
        mid = (start + end) // 2
        if (p <= powerList[mid]):
            end = mid - 1
        else:
            start = mid + 1
    print(nameList[end+1]) # nameList[start]와 동일

그럼 항상 end + 1 == start인 건가~~?