Linear search

Array (배열)

• 정의 : 연속된 주소, 동일한 타입
• 장점 : n개 중 k번째 access가 상수 시간에 가능, Search가 빠름(경우에 따라 다를 수는 있음)
• 단점 : 크기 변화 비용이 크다, Insert, Delete가 느릴 수 있다.
• 사용 : 변화가 없거나 드문 자료에 사용함

---

Linear Search (선형 검색)

순서대로 전부 탐색하는 검색 방법

 

출처 : https://www.geeksforgeeks.org/what-is-linear-search/

#include <stdio.h>

int linear_search(int a[], int n, int x){
    for (int i = 0; i < n; i++) if(a[i]==x) return i; // a[i] or *(a + i)
    return -1; // 찾지 못하면 -1을 return 하도록 약속함
}

int main(){
    int a[10] = {2, 4, 5, 8, 9, 10, 1, 3, 7, 6};
    printf("%d\n", linear_search(a, 10, 3));
}

• 찾지 못하면 -1을 return 하도록 약속함
• 배열의 이름은 주소 : a[i] == *(a+i)
• O(n) 
• Sorting이 되면 더 빨리 검색할 수 있음