02_선형 검색(linear search)

- 선형 검색(linear search): 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소 검색

- 복잡도: O(n)

- 검색 종료 조건 ( 둘 중 하나라도 성립되면 종료됨)

① 검색한 값 발견 못하고 배열 끝까지 검색 (-1 반환)

② 검색할 요소 발견 (처음 발견한 요소의 인덱스 반환)

 

- 반복할 때마다 위의 종료 조건 2개를 모두 판단 → 이 비용을 반으로 줄이는 방법 : 보초법

: 검색하고자 하는 키 값을 배열의 맨 마지막 요소로 저장해둠(보초)

→ 사용자가 길이 7인 배열을 생성한다고 하면, 길이가 8인 배열을 만들어서 마지막요소에 보초 저장해둠

: 값을 찾으면, 그 값이 보초인지 아닌지 확인 (보초면 검색 실패이므로 -1 반환)

: 위의 검색 종료 조건 ①번 필요없어짐

static int seqSearch(int[] arr, int n, int key) {
    arr[n] = key;
    int i = 0;
    for (i = 0; i < n; i++)
        if (arr[i] == key)
            break;
    return i == n ? -1 : i;
}