[자료구조/알고리즘]선형구조 자료 탐색법

선형 구조 자료 탐색법

📌 순차 탐색(Sequential Search)

• 데이터의 처음부터 끝까지 순차적으로 비교하여 원하는 데이터를 찾아내는 알고리즘
• 단순하지만 비효율적이라는 단점이 있음
• 평균적으로 (n+1)/2번의 비교를 거치고, 전부 탐색해야하는 최악의 경우 n번의 비교, 이때 시간 복잡도 O(n)
• 단방향으로 탐색을 수행하기 때문에 선형 탐색이라고도 함

📌 이분 탐색(Binary Search)

• 정렬되어 있는 배열에서 데이터를 찾을 때 사용하는 알고리즘
• 특정 상황에서 순차 탐색보다 더 빠른 속도를 기대할 수 있음
• 모든 데이터를 확인하는 것이 아니라, 탐색 범위를 절반으로 줄여가는 탐색 방법
• 가운데부터 탐색을 시작한다는 특징
• 시간 복잡 O(log2 N)

이분 탐색 Ex) 배열 1 3 4 7 8 13 17에서 '8'이 있는 위치를 찾는다고 가정

배열: 1 3 4 7 8 13 17

1. 가운데 값인 7을 선택
   1 3 4 7 8 13 17

2. 7<8 이므로 더 큰 숫자가 있는 오른쪽으로 진행
   7 8 13 17

3. 7~17의 배열중 가운데인 13을 선택
   7 8 13 17

4. 13>8 이므로 더 작은 숫자가 있는 왼쪽으로 진행
   7 8 13

5. 7과 13의 가운데에 있는 8을 선언
   7 8 13

6. 8=8 이고 배열은 5번째이므로 답은 5

• 모든 입력코드가 오름차순으로 정렬되어 있다는 조건이 있어야한다.

//헤더 부분
int solve(int,int);
//소스 부분
int A[500]; //총 500개까지 담을 수 있는 배열에서 탐색.
int k; //탐색할 값.

int solve(int s, int e);
{
    int m;
    while(e-s>=0)
    {
        m=(s+e)/2; 값이 있을 가능성이 있는 값의 가운데 값.
        if(A[m]==k)
            return m+1; //그 값이 만약 탐색할 값이면 그 위치를 리턴.
        if(A[m]<k) s=m+1; //만약 A[m]이 작으면 좀 더 큰 값들이 있는 오른쪽이 탐색되도록 변경.
        else e=m-1; //아까와 정반대.
    }
    return -1; //찾는 값이 없을 경우 -1을 준다.
}

출처 : https://satisfactoryplace.tistory.com/39