검색 알고리즘 사용하기
많은 검색 알고리즘 중에서 학습용으로 가장 권장하는 이진 검색 알고리즘을 사용하여 배열에서 특정 데이터를 검색하는 기능을 코드로 구현해 보겠습니다. 검색 알고리즘을 적용하면 주어진 데이터에서 특정 데이터를 찾을 수 있습니다.
정렬된 데이터를 이진 검색(이분 탐색)을 사용하여 검색: SearchAlgorithm.cs
using System;
class SearchAlgorithm
{
static void Main()
{
//① 입력
int[] data = { 1, 3, 5, 7, 9 }; //오름차순으로 정렬되었다고 가정
int N = data.Length;
int search = 3; //검색할 데이터: Console.ReadLine() 등으로 가져오기
bool flag = false; //플래그 변수: 찾으면 true, 찾지 못하면 false
int index = -1; //인덱스 변수: 찾은 위치
//② 처리: 이진 검색: Full Scan -> Index Scan
int low = 0; //min: 낮은 인덱스
int high = N - 1; //max: 높은 인덱스
while (low <= high)
{
int mid = (low + high) / 2; //중간 인덱스 구하기
if (data[mid] == search)
{
flag = true; index = mid; break; //찾으면 플래그, 인덱스 저장 후 종료
}
if (data[mid] > search)
{
high = mid - 1; //찾을 데이터가 작으면 왼쪽 영역으로 이동
}
else
{
low = mid + 1; //찾을 데이터가 크면 오른쪽 영역으로 이동
}
}
//③ 출력
if (flag)
{
Console.WriteLine($"{search}을(를) {index}위치에서 찾았습니다.");
}
else
{
Console.WriteLine("찾지 못했습니다.");
}
}
}
실행 결과
3을(를) 1위치에서 찾았습니다.
이진 검색 알고리즘은 정렬된 데이터를 검색하는데, 찾으려는 값보다 작거나 클 때 반씩 나누어서 검색합니다. 따라서 순차 검색보다 검색 효율이 상당히 좋습니다.