파이썬 탐색 구현

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.

반복문을 통해 구현한다.

# 리스트 내에서 목표하는 값을 찾은 후에 그 인덱스를 반환한다.
# 만약, 그 값을 찾지 못하면 -1을 반환한다.
def sequential_search(target, array):
    for index, element in enumerate(array):
        if element == target:
            return index
    return -1

이진 탐색

이진 탐색은 이미 데이터가 정렬되어 있을 경우에만 사용할 수 있다.

리스트 안에 있는 특정한 데이터를 찾기 위해 시작점과 끝점 중간에 중간점을 설정하고 중간점의 데이터를 확인한다.

중간점의 데이터가 찾는 값보다 작을 경우에는 끝점을 중간값의 이전값으로 옮기고,

중간점의 데이터가 찾는 값보다 큰 경우에는 시작점을 중간값의 이후값으로 옮기고, 이를 반복한다.

반복문을 사용하여 구현하는 방법과 재귀함수로 구현하는 방법이 있지만, 반복문을 사용하여 구현하는 방법이 좋다.

(파라메트릭 서치에 보다 더 유용하기 때문이다.)

# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end)//2
        # 중간점의 데이터가 일치하는 경우 바로 반환
        if array[mid] == target:
            return mid
        # 중간값이 찾으려는 값보다 큰 경우 범위를 왼쪽으로 한정(중간값 이후로는 볼 필요가 없다)
        elif array[mid] > target:
            end = mid - 1
        # 중간값이 찾으려는 값보다 작은 경우 범위를 오른쪽으로 한정(중간값 이전은 볼 필요가 없다)
        elif array[mid] < target:
            start = mid + 1
    # 시작점이 마지막점보다 커진 순간 모든 데이터를 확인한 것이며, 값을 찾을 수 없었음
    return None

# 재귀 함수로 구현한 이진 탐색
def binary_search(array, target, start, end):
    # 값을 찾을 수 없는 경우 None 반환
    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)
    # 찾으려는 값보다 중간값이 작은 경우 오른쪽을 확인(왼쪽은 볼 필요가 없다)
    elif array[mid] < target:
        return binary_search(array, target, mid+1, end)