탐색기반 알고리즘 설계_1.선형구조탐색

※ 탐색이란?

  - 같은 형태의 한 개 이상의 자료들이 모여 있는 집합에서 특정 자료를 찾는 모든 작업
  - 탐색할 자료가 저장되어 있는 구조를 먼저 파악하는 것이 중요
    (탐색 구조가 직접적으로 드러난 경우는 쉬운문제, 직접 드러나지는 않으나 문제 해결과정에서 자체적으로 구조화하며 탐색하는 경우 중급 이상 문제)

※ 탐색기반설계

  - 주어진 문제에서 주어진 데이터를 특성에 맞도록 구조화하고 이 자료를 적절한 방법으로 탐색해 나가면서 원하는 해를 찾는 알고리즘 설계법
  - 전체를 탐색하는 전체탐색법과 탐색할 영역을 적절한 방법으로 배제하여 탐색의 효율을 높은 부분탐색법이 있다.

※ 탐색이 되는 구조

  - 선형구조 : 배열이나 연결리스트로 표현될 수 있는 구조
  - 비선형구조 : 트리나 그래프의 형태로 표현되는 구조

 

1. 선형구조 탐색

 - 자료의 순서를 유일하게 결정할 수 있는 형태의 구조
 - i번째 자료를 탐색한 다음, i+1번째로 탐색, 탐색해야할 자료가 유일한 형태
 - 2차원/3차원 구조라도 순서가 일정하면 선형
 - 선형구조의 탐색에는 순차탐색과 이분탐색이 존재하며, 이들을 적절히 사용한 탐색법도 만들어 사용 가능

[순차탐색] (1)->(2)->(3)->(4)->(5)->(6)

 

 

[이분구조탐색] 기준정을 중심으로 탐색

- 이분탐색 소스

#include<stdio.h>
 
int S[100], n, k;
 
int find(int s, int e)
{
    while(s<=e)
    {
        int m=(s+e)/2;
        if(S[m]==k) return m;
        if(S[m]>k) e=m-1;
        else s=m+1;
    }
    return -1;
}
 
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++)
    {
        scanf("%d", &S[i]);
    }
    printf("%d\n", find(0, n-1));
    return 0;
}
 

 

- 이분탐색 _ 반복문 & 재귀

//반복문
int solve(int s, int e)
{
    if (s > e)    return -1;
 
    int m = (s + e) / 2;
    if (S[m] == k)    return m + 1;
 
    if (S[m] < k)
        return solve(m + 1, e);
    else
        return solve(s, m - 1);
}
 
//재귀
int solve(int s, int e)
{
    int m;
    while (e - s >= 0)
    {
        m = (s + e) / 2;
        if (S[m] == k)
            return m + 1;
        if (S[m] < k) s = m + 1;
        else e = m - 1;
    }
    return -1;
}