[Jungle] Week1. 이진탐색, 완전 탐색, 분할 정복

정글 week01. 핵심 키워드

1. 완전 탐색(Brute Force): 가능한 모든 경우의 수를 탐색 - 모든 경우를 하나씩 검사
2. 이분탐색(Binary Search): 정렬된 배열에서 특정한 값을 찾는 탐색 알고리즘
   

• 배열의 중간 값을 선택하여 찾고자 하는 값과 비교
• 찾고자 하는 값이 중간 보다 작으면 왼쪽을,
• 중간값 보다 크면 오른쪽 탐색
• 배열의 크기를 반으로 줄여가며 위치를 찾기 때문에 시간 복잡도는 O(log n)
• 이미 정렬된 리스트에 한해서만 가능하다!

재귀함수

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

def binary_search(left, right):
    if left > right:
        return -1
    else:
        mid = (left + right) //2
        if S[mid] == x:
            return mid
        elif S[mid] > x:
            return binary_search(left, mid - 1)
        elif S[mid] < x:
            return binary_search(mid+1, right )


print(binary_search(0, n-1))

반복문

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

from typing import Any, Sequence
def binary_search(a: Sequence, key: Any):
    left = 0
    right = len(a) -1

    while True:
        mid = (left + right) //2

        if a[mid] == key:
            return mid
        elif a[mid] < key:
            left = mid + 1
        else:
            right = mid - 1

        if left > right:
            return -1 #키가 없음 검색 실패

3. 분할 정복:

function F(x):
  if F(x)가 간단 then:
    return F(x)를 계산한 값
  else:
    x 를 x1, x2로 분할
    F(x1)과 F(x2)를 호출
    return F(x1), F(x2)로 F(x)를 구한 값

• 분할: 문제를 작은 하위 문제로 분할
• 정복: 각 하위 문제는 재귀적으로 해결
• 결합: 하위 문제의 해결책을 결합하여 해결

예시) 병합 정렬(merge sort), 이분 탐색(binary search), 거듭 제곱 연산 등