탐색 알고리즘 총 정리(선형,이진탐색,해시탐색)

탐색 알고리즘이란

탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법

 

01 선형 탐색(Linear Search)

처음부터 끝까지 하나씩 비교하면서 찾는 방식

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

시간복잡도

최악 : O(N)

최선 : O(1)

---

02 이진 탐색(Bineary Search)

정렬된 배열에서 중간값과 빅하며 절반씩 범위 줄이기

조건 : 오름차순 or 내린차순으로 정렬된 데이터여야 한다.

출처 : https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm

int BinarySearch(int[] arr, int target)
{
    int left = 0, right = arr.Length - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

시간복잡도

O(logn)

---

03 해시 탐색(Hashing)

키(key)를 해시함수로 변환해서 바로 인덱스로 접근

Dictionary<string, Item> itemMap = new();
itemMap["sword"];

시간복잡도

평균 : O(1)

최악(충돌 발생시) : O(N)