순차 검색(Sequential Search)

순차 검색은 일렬로 되어 있는 자료를 처음부터 마지막까지 순서대로 검색하는 방법으로 선혈 검색(Linear Search)이라고도 한다. 순차 검색은 가장 간단하고 직접적인 방법으로 배열이나 연결 리스트로 구현된 선형 자료 구조에서 원하는 항목을 찾는 방법이다. 순차 검색은 검색해야 하는 자료의 양에 따라 효율이 달라지기 때문에 자료가 아주 많은 경우에는 비효율적이지만, 알고리즘이 단순하여 구현이 쉬운 장점이 있다.

- 정렬되지 않은 순차 자료 구조에서의 순차 검색

첫 번쨰 원소부터 시작하여 마지막 원소까지 순서대로 키값이 일치하는 원소가 있는지를 비교하여 찾는다. 키값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다. 마지막 원소까지 비교하여 키값이 일치하는 워소가 없으면 검색실패

시간복잡도 : O(n)

public class sequentialSearch1 {

public static void main(String[] args) {

int a[]={8,30,1,9,11,19,2};

int size=a.length;

sequentialSearch(a,size,9);

sequentialSearch(a,size,10);

}

static void sequentialSearch(int a[], int n, int key)

{

int i;

for(i=0 ; i<n ;i++){

if(a[i]==key) {

break;

}

}

if(i<n){

System.out.println(i+1+"번째에서 검색 성공");

}

else System.out.println("검색 실패");

}

}

- 정렬되어 있는 순차 자료 구조에서의 순차 검색

정렬되어 있지 않은 자료에서 순차 검색을 하는 경우에 검색 실패는 마지막 원소까지 모두 비교한 후에야 알 수 있다. 하지만 정렬되어 있는 자료에 대해 순차 검색을 할 경우에는 원소의 키값이 찾는 키값보다 크면 찾는 원소가 없는 것이므로 더 이상 검색을 수행하지 않고 끝낼 수 있다.

시간복잡도 : O(n)

public class sequentialSearch2 {

public static void main(String[] args) {

int a[]={1,2,8,9,11,19,29};

int size=a.length;

sequentialSearch(a,size,8);

sequentialSearch(a,size,6);

}

static void sequentialSearch(int a[], int n, int key) {

int i=0;

if(i<n){

while( a[i]<key) i++;

}

if( a[i]==key){

System.out.println(i+1+"번째에서 검색 성공");

}

else System.out.println(i+1+"번째에서 검색 실패");

}

}