Searching 알고리즘이란?

Searching 알고리즘 의미

정렬되어 있는 자료구조에서 원소를 찾는 방법이다.

 

Searching 알고리즘 분류

1.Linear Search

    가장 쉬운 Searching 알고리즘이다. 

    Sequential Search 알고리즘이다.

    리스트의 한쪽 끝에서 시작해서 원소를 찾을 때가지 진행한다.

2.Binary Search

    배열을 반으로 나눠서 찾는 것을 반복한다.

    배열이 정렬됐다는 정보를 이용해서 시간 복잡도를 O(Log n base 2)으로 줄인다.

3.Ternary Search

    배열을 3개로 나눠서 찾는 것을 반복한다.

    Binary Search와 비슷하나 시간 복잡도가 O(Log n base 3)가 줄어든다는 차이가 있다.

4.Jump Search

    일정 간격으로 건너 뛰면서 찾는 것을 반복한다.

    성능은 linear search < jump search < binary search 이다.

5.Interpolation Search

    Binary Search를 개선한 알고리즘이다. 

    Interpolation은 새로운 데이터 포인터를 만든다.

 

참고

https://www.geeksforgeeks.org/searching-algorithms/?ref=lbp