[4]

1. 선형검색(순차검색)

: 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 맨 앞에서부터 순서대로 요소를 검색

int search(const int a[], int n, int key){
        int i;
        for(i=0; i<n; i++)
                if(a[i] == key)
                        return i;
        return -1;
}

선형검색에서 보초법 사용

#include<stdio.h>

int search(const int a[], int n, int key){
        int i=0;
        a[n] = key;
        while(1){
                if(a[i] ==key)
                        break;
                i++;
        }
        return i == n ? -1 : i;
}

2. 이진검색

:중앙 요소에 pc를 놓고 key값과 크기를 비교하여 이동하며 검색하는방식.

int search(const int a[], int n, int key){
        int pl=0;
        int pr = n-1;
        int pc;
        do{
                pc=(pl+pr)/2;
                if(a[pc] == key) return pc;
                else if(a[pc]<key) pl=pc+1;
                else pr=pc-1;
        }while(pl<=pr);
        return -1
}

3. 복잡도

: 알고리즘의 성능을 객관적으로 평가하는 기준
1. 시간 복잡도: 실행에 필요한 시간을 평가한 것.
2. 공간 복잡도: 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것.

특정 코드가 n/2번 실행됐을 때 복잡도는 O(n), 1번만 실행되면 O(1)

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시한다.

O(f(n)) + O(g(n)) = O(max(f(n),g(n)))