[알고리즘] 탐색

탐색 관련 개념

• 선형탐색 & 순차적 탐색 [O(n)]
  : 리스트의 요소들을 처음부터 순차적으로 탐색하여 원하는 값을 찾는 방법이다
  원하는 값이 발견되지 않을 경우 배열에 있는 모든 원소를 전부 검사한다.

이진 탐색 [O(logN)]

• 크기순으로 정렬된 성질을 이용하기 때문에 이미 정렬되어 있는 배열에서 사용할 수 있는 방법이다.
• 배열의 중간의 양옆 값을 확인하여, 원하는 데이터가 어디에 속하는지 점점 좁혀나가는 방법이다.

# 원하는 값이 90
# 원하는 값이 50(1차 탐색 중간 값)보다 큰 상황, 2차 탐색 시 51(lower) ~ 100(upper) 탐색

1 2 3 4 5 ... 47 48 49 50 51 52 53 ... 99 100

# 원하는 값이 75(2차 탐색 중간 값)보다 큰 상황, 2차 탐색 시 75(lower) ~ 100(upper) 탐색
51 52 53 ... 74 75 76 ... 99 100

# 원하는 값이 87 (3차 탐색 중간 값)보다 큰 상황, 2차 탐색 시 87(lower) ~ 100(upper) 탐색
75 76 ... 86 87 88 ... 99 100

... 반복

배열의 크기가 커질수록 동작시간이 기하급수적으로 커지는 선형 탐색 & 순차적 탐색에 비해 이진 탐색 방식은 배열의 크기가 동작시간에 큰 영향을 주지 않는다.
하지만, 이미 정렬된 배열이 우선적으로 필요하기 때문에 일회성으로 사용되는 데이터에서 값을 찾을 때보다 주기적으로 데이터 탐색이 필요한 데이터 목록에서 사용하면 좋다.
왜냐하면 일회성으로 탐색 후 사용하지 않는 데이터에서 굳이 정렬을 추가로 해 줄 필요는 없기 때문이다.

ex) 반복문을 이용한 탐색

• 중간 값보다 타겟이 작을 경우 왼쪽을 탐색, 크다면 오른쪽 부분을 탐색
• start, end를 조정하며 탐색할 배열의 범위를 조절한다.

def binary_search(array, target):

    start = 0  # 탐색 범위 시작
    end = len(array) - 1  # 탐색 범위 끝

    # 만약 탐색
    while start <= end:

        # 중간 인덱스 구하기
        middle = (start + end) // 2

        # target 값을 찾았을 때
        if array[middle] == target:
            print(f"{target} is {middle} index")
            return

        # 만약 탐색 값이 중간 값보다 크다면
        # 다음 탐색 부분은 중간 인덱스 다음 ~ 마지막 인덱스
        elif array[middle] < target:
            start = middle + 1

        # 만약 탐색 값이 중간 값보다 작다면
        # 다음 탁색 부분은 처음 인덱스 ~ 중간 인덱스 직전
        elif array[middle] > target:
            end = middle - 1

    # 이진 탐색을 마치고도 target 값을 찾지 못했다면
    print(f"Can't search {target} in array")
    return -1

ex) 재귀를 이용한 탐색

• 재귀를 사용하여, 분할 정복 방법으로 탐색할 배열의 범위를 조절한다.

def binary_search(array, target, start, end):

    # 이진 탐색을 마치고도 target 값을 찾지 못했다면
    if start > end:
        print(f"Can't search {target} in array")
        return False

    # 중간 인덱스 구하기
    middle = (start + end) // 2

    # target 값을 찾았을 때
    if array[middle] == target:
        print(f"{target} is {middle} index")

    # 만약 탐색 값이 중간 값보다 크다면
    # 다음 탐색 부분은 중간 인덱스 다음 ~ 마지막 인덱스
    elif array[middle] < target:
        binary_search(array, target, middle + 1, end)

    # 만약 탐색 값이 중간 값보다 작다면
    # 다음 탁색 부분은 처음 인덱스 ~ 중간 인덱스 직전
    elif array[middle] > target:
        binary_search(array, target, start, middle - 1)

    else:
        return False