탐색

탐색은 리스트의 요소 중 자신이 원하는 값을 찾는 알고리즘이다.

정렬과 마찬가지로 탐색도 아주 다양한 방법이 존재한다.

이 페이지에서는 선형 탐색과 이진 탐색만 정리하겠다.

1. 선형 탐색 (Linear Search)

배열이나 리스트의 첫 번째 요소부터 순차적으로 원하는 값을 찾는 방법이다. 평균 시간복잡도는

O(n)

이고, for문 1번으로 구현이 가능하다.

아래는 C++로 구현된 선형 탐색 코드이다.

c++

// 배열은 arr[]이라 가정
for (i = 0; i < arr.size(); i++) {
    if (arr[i] == target)
        return i;
}

2. 이진 탐색 (Binary Search)

정렬이 된 리스트에서만 사용할 수 있다. 중간 원소를 기준으로 찾고자 하는 값이 어느쪽에 있는지 범위를 절반씩 줄여 나가는 방법이다. 평균 시간복잡도는

O(logn)

이고, while 문을 사용하여 값이 일치할 때 까지 범위를 절반으로 나눈다.

아래는 C++로 구현된 이진 탐색 코드이다.

c++

//배열은 arr[]이라 가정
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        // 중간 인덱스 계산
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target)
            return mid;  // 목표 값 발견
        else if (arr[mid] < target)
            left = mid + 1;  // 오른쪽 반으로 이동
        else
            right = mid - 1;  // 왼쪽 반으로 이동
    }
    return -1;  // 목표 값이 없는 경우
}

left와 right 2개의 값과 각 반복마다 평균을 이용해 mid를 계산하여 target이 존재할 수 있는 범위로 left와 right를 mid로 바꾸며 범위를 조정해나간다. mid가 target이 되었다면 이진 탐색이 끝나게 된다.

3. 그 외의 탐색

이 이상의 탐색은 한 페이지에 정리하기에는 내용이 너무 많으므로 각각의 페이지를 따로 만들어 서술하였다.