● 탐색 알고리즘
- 데이터 집합에서 특정 항목을 찾는 방법을 제공
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;
}
'C# 알고리즘' 카테고리의 다른 글
트리 (Tree) (0) | 2023.11.15 |
---|---|
그래프 (Graph) (1) | 2023.11.15 |
정렬 알고리즘 (0) | 2023.11.15 |
시간 복잡도와 공간 복잡도 (0) | 2023.11.15 |
알고리즘 (0) | 2023.11.15 |