[Python] 선형 탐색(Linear Search) 이진 탐색 (Binary Search)

 

선형 탐색 (Linear Search)

 

 

선형 탐색은 배열 또는 리스트의 처음부터 끝까지 차례대로 요소를 비교하여 원하는 값을 찾는 방법입니다.

시간 복잡도는 O(n)입니다.

 

선형 탐색은 정렬되지 않은 데이터나 작은 데이터 셋에 간단히 적용 가능합니다.

 

예시 코드

 

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

# 사용 예제
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)

 

---

 

이진 탐색 (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  # 찾지 못한 경우 -1 반환

# 사용 예제
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 7
result = binary_search(arr, target)

if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found in the array")