1# | 순차 탐색, 이진탐색, 빅-오 표기법

순차 탐색 (Linear Search) 

#include<stdio.h>
 
int Lsearch(int ar[],int len, int target)
{
    int i;
    for(i=0; i<len,i++)
    {
        if (ar[i]==target)
            return i;            // 찾은 대상 인덱스 값 
    }
    return -1;    //찾지 못했을 때
 
}

이진 탐색(Binary Search)

#include<stdio.h>
int Bsearch(int ar[],int len, int target)
{
    int first =0; 
    int last =0;
    int mid =0;
    
    while(first <= last)
    {
        mid = (first+last ) /2 ;
        
        if (target == ar[mid])
        {
            return mid;
        }
        else
        {
             if(target <ar[mid])
                 last = mid -1;
            else 
                first = mid +1;
                
        }
    }
    return -1;
}

이진 탐색은 정렬된 데이터가 아니면 적용이 불가능 하다.  

코드 설명 : 

1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.

2. 0과 8을 합하여 그 결과를 2로 나눈다.

3. 2로 나눠서 얻은  결과 4 를 인덱스 값으로 하여 ar[4]에 저장된 값이 3인지 확인한다.

4. ar[4]에 저장된 값 9와 3의 대소를 비교한다.

5. 결과는ar[4] > 3이므로 탐색의 범위를 인덱스 기준 0~3 으로 제한한다.

6.   2. 와 같은 순서를 계속 반복한다.

빅-오 표기법(Big-Oh Natation)

'데이터 수의 증가' 에 따른 '연산횟수 증가 현태를 표현한 것' 

단순하게 빅- 오 구하기 ▶ "T(n)이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다."

T(n)  = n^2 + 2n+9   ▶  O(n^2)

빅-오 표기들의 성능의 대소

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)