탐색 알고리즘

● 탐색 알고리즘
 - 데이터 집합에서 특정 항목을 찾는 방법을 제공

 

1. 선형 탐색
 - 가장 단순한 탐색 알고리즘
 - 배열의 각 요소를 하나씩 차례대로 검사

 - 배열이 정렬되어 있지 않는 경우에 사용
 - 시간 복잡도 : 최악의 경우 O(n)

 

int SequentialSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }

    return -1;
}

2. 이진 탐색
 - 정렬이된 배열에서 빠르게 원하는 항목을 찾는 방법
 - 중간 요소와 찾고자하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽, 크면 오른쪽 탐색

 - 중앙값과 비교하여 탐색 범위를 반으로 줄이는 방법으로 빠른 검색이 가능
 - 시간 복잡도 : 최악의 경우 O(log n)

 

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return -1;
}