탐색 / 선형구조 탐색

 

i번째 자료를 탐색한 다음, i+1번째로 탐색해야할 자료가 유일한 형태를 의미한다. 2차원, 3차원 구
조라도 순서가 일정하게 정해져 있으면 이는 선형이라고 할 수 있다

 

• 순차탐색

자료의 특성에 관계없이 사용할 수 있는 일반적인 방법으로 전체탐색기법의 한 방법이다. 첫 번째 원소로부터 시작하여 한 원소씩 차례로 다음 원소를 탐색해 나가는 방법으로 자료가 n개 있을 때의 계산량은 O(n)이다.

• 이분 탐색

S 에 n개의 원소를 입력받고, 그 중에 k가 있는지를 찾는 알고리즘이다. 이 알고리즘은 오름차순이나 내림차순으로 정렬된 선형구조에서 원하는 원소를 찾는 것으로 계산량은 O(log2 n)이다.

이분탐색의 탐색순서(○는 처음 접근하는 원소이고, 사각형은 찾은 곳의 값이 찾으려는 값보다 작으면 찾는 위치, 둥근 사각형은 그 값의 반대조건일 경우에 탐색하는 위치이다. 조건의 결과에 따라 왼쪽 또는 오른쪽 중 하나를 탐색하게 된다.)

 

 

2. 비선형구조 탐색