🔗 순차 탐색 알고리즘과 이진 탐색 알고리즘

오늘은 두 가지 탐색 알고리즘인 순차 탐색과 이진 탐색에 대해 알아보려고 합니다. 두 알고리즘 모두 데이터를 탐색하는 방법이지만, 그 작동 방식과 효율성에 큰 차이가 있습니다. 어떤 상황에서 어떤 알고리즘을 사용해야 하는지 함께 살펴보겠습니다.

---

1️⃣ 순차 탐색 알고리즘

순차 탐색은 가장 기본적인 탐색 방법입니다. 리스트나 배열의 첫 번째 요소부터 하나씩 차례대로 탐색하여 찾고자 하는 값을 찾을 때까지 계속 진행합니다.

🛠️ 순차 탐색 과정:

1. 리스트의 첫 번째 요소부터 시작합니다.
2. 각 요소를 순서대로 확인하면서 찾고자 하는 값과 비교합니다.
3. 찾으면 탐색을 종료하고 해당 위치를 반환합니다.
4. 리스트의 끝까지 찾아도 없으면 탐색 실패로 처리합니다.

📈 시간 복잡도:

• 최선의 경우: O(1) (찾고자 하는 값이 첫 번째 위치에 있을 때)
• 최악의 경우: O(n) (리스트의 끝까지 탐색해야 할 때)

✅ 장점:

• 정렬되지 않은 리스트에서도 사용할 수 있습니다.
• 구현이 간단합니다.

❌ 단점:

• 데이터가 많아질수록 탐색 시간이 오래 걸립니다.

코드 예시:

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 찾은 경우 인덱스 반환
    return -1  # 찾지 못한 경우

---

2️⃣ 이진 탐색 알고리즘(Binary Search)

이진 탐색은 정렬된 리스트에서만 사용할 수 있는 매우 효율적인 탐색 방법입니다. 탐색 범위를 절반으로 나누면서 찾고자 하는 값을 찾습니다.

🛠️ 이진 탐색 과정:

리스트가 정렬되어 있어야 합니다.
중간 요소를 확인하고, 찾고자 하는 값이 중간 요소보다 작으면 왼쪽으로, 크면 오른쪽으로 탐색 범위를 줄여나갑니다.
탐색 범위를 계속 절반씩 줄여가면서 값을 찾습니다.
값을 찾으면 탐색을 종료하고, 찾지 못하면 탐색 범위를 모두 확인했으므로 탐색 실패로 처리합니다.

📈 시간 복잡도:

최악의 경우: O(log n) (탐색 범위를 절반씩 줄여나가기 때문)

✅ 장점:

매우 빠른 탐색이 가능합니다.
데이터가 클수록 그 효율성이 극대화됩니다.

❌ 단점:

정렬된 리스트에서만 사용할 수 있습니다.
정렬되지 않은 리스트에서 사용하려면 먼저 정렬을 해야 하므로 추가 시간이 필요할 수 있습니다.
코드 예시:

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  # 찾지 못한 경우

---

마무리 🎯

순차 탐색과 이진 탐색은 각기 다른 장단점을 가지고 있습니다. 작은 데이터셋이나 정렬되지 않은 데이터셋에서는 순차 탐색이 적합하지만, 큰 데이터셋이면서 정렬이 되어 있다면 이진 탐색을 사용하는 것이 훨씬 더 효율적입니다.