배열에서 특정 값 찾기

06 Nov 2023

javascript

배열은 프로그래밍에서 데이터를 저장하고 관리하는 강력한 자료 구조입니다. 때로는 배열에서 특정 값의 존재 여부를 확인하고 싶을 수 있습니다. 이 글에서는 배열에서 특정 값 찾는 방법을 알아보겠습니다.

선형 탐색

가장 간단한 방법으로는 선형 탐색을 사용하는 것입니다. 선형 탐색은 배열의 모든 요소를 하나씩 순회하면서 찾고자 하는 값과 일치하는지 확인하는 방법입니다.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

arr = [1, 3, 5, 7, 9]
target = 5
index = linear_search(arr, target)
if index != -1:
    print(f"{target}의 인덱스는 {index}입니다.")
else:
    print(f"{target}을(를) 찾을 수 없습니다.")

위의 예제 코드는 Python에서 선형 탐색을 구현한 것입니다. 배열을 순회하면서 찾는 값과 일치하는 요소를 찾으면 해당 요소의 인덱스를 반환하고, 일치하는 값이 없다면 -1을 반환합니다.

이진 탐색

이진 탐색은 배열이 정렬되어 있다는 가정하에 사용되는 효율적인 탐색 알고리즘입니다. 이진 탐색은 배열의 중간 요소와 찾고자 하는 값을 비교하여 탐색 범위를 좁혀나가는 방식으로 동작합니다.

def binary_search(arr, target):
    left = 0
    right = 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

arr = [1, 3, 5, 7, 9]
target = 5
index = binary_search(arr, target)
if index != -1:
    print(f"{target}의 인덱스는 {index}입니다.")
else:
    print(f"{target}을(를) 찾을 수 없습니다.")

위의 예제 코드는 Python에서 이진 탐색을 구현한 것입니다. 배열을 중간 요소와 찾는 값과 비교하면서 탐색 범위를 좁혀가고, 일치하는 값을 찾으면 해당 요소의 인덱스를 반환합니다. 만약 일치하는 값이 없을 경우에는 -1을 반환합니다.

결론

배열에서 특정 값을 찾는 방법에 대해 알아보았습니다. 선형 탐색은 간단하지만 배열의 크기에 비례해 시간 복잡도가 증가하는 단점이 있습니다. 이진 탐색은 배열이 정렬되어 있어야 하지만, 효율적인 탐색을 제공합니다. 실제 상황에 맞게 적절한 탐색 알고리즘을 선택하여 사용하는 것이 중요합니다.

선형 탐색

이진 탐색

결론

Reference