Searching Algorithms

배열의 처음부터 끝까지 순서대로 모든 요소를 확인하며 원하는 값을 찾는 가장 기초적인 검색 방법입니다.

정렬된 배열에서 중간값을 반복적으로 비교하여 탐색 범위를 반으로 줄여가는 매우 빠르고 뛰어난 성능의 검색 알고리즘입니다. 매 반복마다 후보 공간을 절반으로 축소해 로그 스케일의 비교 횟수만으로 값을 찾아냅니다.

정렬된 배열을 √n 크기의 블록으로 점프하며 탐색 범위를 빠르게 좁힌 뒤, 후보 블록 내부에서 선형 탐색을 수행합니다. 이진 탐색보다 점프 비용은 크지만, 역방향 이동이 비싼 저장 매체(자기 테이프·디스크)에서 유리합니다.

인덱스를 2의 지수로 확장(1, 2, 4, 8, …)하여 Target을 포함하는 구간을 빠르게 특정한 뒤, 해당 구간에서 이진 탐색을 수행합니다. 길이를 알 수 없는 무한/무경계 스트림 탐색에 강점이 있습니다.

값의 분포가 균등하다고 가정하고 Target의 '위치'를 비례 계산으로 추정합니다. 균등 분포에서는 이진 탐색보다 빠르지만, 편향된 분포에서는 최악 O(n)까지 퇴화할 수 있습니다.

구간을 3등분하여 두 개의 중간 지점(mid1, mid2)으로 세 구간을 한 번에 판별합니다. 이진 탐색보다 재귀 깊이는 얕지만 반복당 비교 횟수가 많아, 실제로는 유니모달 함수의 극값 탐색에 주로 사용됩니다.

피보나치 수열을 이용해 구간을 분할합니다. 나눗셈 없이 덧셈·뺄셈만으로 인덱스를 계산하므로, 나눗셈이 비싼 하드웨어나 CPU 캐시 친화적 접근이 필요한 환경에서 이진 탐색보다 빠를 수 있습니다.

Queue(FIFO)를 사용해 가까운 노드부터 층층이(level-order) 확장하는 그래프 탐색 알고리즘입니다. 무가중치 그래프에서 최단 경로를 보장하며, 최단 거리·컴포넌트 탐지·위상 정렬의 기반이 됩니다.

Stack(LIFO)을 사용해 한 경로를 최대한 깊게 파고든 뒤 막히면 되돌아오는(backtrack) 그래프 탐색 알고리즘입니다. 메모리 사용량이 적고(O(h)) 사이클 탐지·위상 정렬·백트래킹 기반 문제 해결의 핵심이 됩니다.

f(n) = g(n) + h(n) 이 가장 작은 노드를 우선 확장하는 휴리스틱 기반 최단 경로 알고리즘입니다. 휴리스틱이 admissible 하면 최적 경로를 보장하며, 경로 탐색·게임 AI·로봇 내비게이션의 표준 도구입니다.