[Python]완전탐색/이분탐색

완전탐색

• Brute Force라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성 관점에서 최악의 방법
• 반복문으로 구현

def solution(trump):
    for i in range(len(trump)):
    if trump[i] == 8 :
        return i
    return -1

• 재귀함수로 구현

def solution(trump, loc):
    if trump[loc] == 8 :
        return loc
    else :
        return solution(trump, loc+1)

이분탐색

• 이진검색이라고도 하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘
• 중간의 값을 선택하여 찾고자 하는 값의 크고 작음을 비교하는 방법

def solution(trump):
    left = 0
    right = len(trump)-1

    # left가 right보다 작거나 같다면
    while(left<=right):
        mid = (left+right) // 2  # mid 값 계산
    if trump[mid] == 8:
        return mid  # 정답일 경우 정답 반환
    elif trump[mid] < 8:
        left = mid + 1  # 정답보다 작을 경우 left를 mid+1로 이동
    elif trump[mid] > 8:
        right = mid -1  # 정답보다 클 경우 right를 mid-1로 이동

    return mid