탐색 알고리즘 : 순차 Sequential / 이진 Binary / 삼분 Ternary

순차 탐색 알고리즘 / Sequential Search

 

차례로 확인하며 찾고자 하는 값을 탐색

Sequential Search Algorithm

Pseudo code of Sequential Search Algorithm

정수 n에 대한 inderx에서 x 값을 찾는 순차 탐색

Index S는 [1:n]으로 

{

1부터 시작해서

while( 현재 위치가 n보다 작거나 같고, 찾고자 하는 x 값이 아니라면 )

현재 위치에서 +

 

if(만약 현재 위치가 n보다 커지면, x 값을 못 찾았기에 0를 출력)

else ( 찾고자 하는 x 값을 찾으면, 현재 위치를 출력 )}

 

 

---

 

순차 탐색 vs 이진 탐색

이진 탐색

 

 

가정 : 감소하지 않는 배열로 정렬되어 있어야 함.

 

Pseudo code of Binary Search Algorithm

 

 

정수 n에 대한 inderx에서 x 값을 찾는 이진 탐색

Index S는 [1:n]으로 

{

index location, low, high, mid

low = 1, high = m, location = 0;

while( low 위치가 high보다 작거나 같고,  위치값이 0이면, ){

mid = low + high / 2;

만약 찾고자 하는 x 값이 mid와 같다면

현재 위치 mid 값을 출력

else if 찾고자 하는 x 값이 < mid값 보다 작으면

high의 값을 mid -1 로 저장

else 찾고자 하는 x 값이 > mid값보다 크면

low의 값을 mid+1로 저장

 

 

---

 

삼분 탐색 / Ternary Search Algorithm

 

오목하거나 볼록한 수열에서 극 값, 즉 최솟값 또는 최댓값을 찾는 Search Alogrithm

 

Pseudo code of Ternary Algorithm

 

 

 

 

 

참고문헌

 

Richard Neapolitan, 「Foundations Of Algorithms」

Thomas H. Cormen et al., 「Introduction to Algorithms」

https://mjmjmj98.tistory.com/142

[알고리즘] 이진 탐색(Binary Search)

https://mingnine9999.tistory.com/34

삼분탐색..!!(Ternary search)

https://velog.io/@blankspxcx/%EC%82%BC%EB%B6%84-%ED%83%90%EC%83%89-Tenary-Search

삼분 탐색 (Tenary Search)

 

---

⊙ 이 글은 개인 공부를 목적으로 작성된 글입니다.

⊙ 내용에 대한 오류나 피드백 감사히 받고 있습니다 !