검색 알고리즘이란?

검색 알고리즘은 주어진 데이터에서 특정 값을 찾는 알고리즘이다. 다양한 검색 알고리즘이 있지만, 가장 널리 사용되는 두 가지 검색 알고리즘인 선형 검색(Linear Search)과 이진 검색(Binary Search)이 있다. 이진 검색은 정렬된 데이터에서 효과적으로 동작하므로, 데이터가 정렬되어 있는 경우에 사용하는 것이 좋다. 반면 선형 검색은 정렬 여부에 상관없이 동작하며, 작은 데이터 집합에서는 성능 상의 차이가 크게 나타나지 않을 수 있다.

선형 검색(Linear Search)

선형 검색은 가장 간단한 형태의 검색 알고리즘 중 하나이다.

주어진 리스트나 배열에서 원하는 값을 찾기 위해 처음부터 끝까지 순차적으로 탐색한다.

찾으려는 값을 찾거나 리스트의 끝에 도달할 때까지 반복한다.
선형 검색은 데이터가 정렬되어 있지 않아도 동작하며, 리스트나 배열의 모든 요소를 확인하기 때문에 데이터 크기에 비례하여 시간이 걸릴 수 있다.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 찾은 값의 인덱스를 반환
    return -1  # 찾는 값이 리스트에 없을 경우 -1을 반환

이진 검색(Binary Search)

이진 검색은 정렬된 리스트나 배열에서 원하는 값을 효율적으로 찾는 알고리즘이다.
중앙값을 선택하고 이를 기준으로 찾으려는 값이 중앙값보다 큰지 작은지를 비교한다.
찾으려는 값이 중앙값보다 작으면 중앙값의 왼쪽 부분을 대상으로 검색하고, 크면 오른쪽 부분을 대상으로 검색한다.
이 과정을 반복하여 원하는 값을 찾거나 검색 범위가 더 이상 없을 때까지 수행한다.
이진 검색은 평균적으로 선형 검색보다 훨씬 빠르게 동작하며, 검색 대상이 정렬되어 있어야 한다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 찾은 값의 인덱스를 반환
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 찾는 값이 리스트에 없을 경우 -1을 반환