순차 탐색 , 이진 탐색

앞에서 차례대로 탐색

// 순차 탐색 알고리즘
int  Lsearch(int ar[], int len, int target) 
{
    int  i;
    for( i = 0 ;   i <len ; i++ )      {
            if(ar[i] == target)
                 return i;       // 찾은 대상의 인덱스 값 반환      
    }
    return -1;       // 찾지 못했음을 의미하는 값 반환 
}

•찾는 데이터가 처음에 있다:  최상의 경우 --> 연산의 수 = 1

•찾는 데이터가 없거나 가장 끝에 있다: 최악의 경우 ---> 연산의 수 = n

•가장 현실적인 경우는? 평균의 경우!

 

                                                ↑

---

 

이진 탐색 

이미 정렬된 배열에서 검색

이진 탐색

1. 정 가운데 위치 찾기

2. 원하는 데이터인지 비교

-> y : 반환

-> N: 앞 또는 뒤 부분을 검색 대상으로 좁힌다. (검색 대상이 반으로 줄어든다!!)

 

 int BSearch(int ar[], int len, int target)  {
        int first = 0;        // 탐색 대상의 시작 인덱스 값
        int last = len-1;        // 탐색 대상의 마지막 인덱스 값
        int mid;

        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;        // 찾지 못했을 때
}

이진 탐색 알고리즘의 재귀 구현

int	BSearchRecur(int  ar[], int first, int last, int target)
{
    int mid; //가운데 위치

    if (first > last)
        return -1; //데이터 한 개 이상일 때
    mid = (first + last) / 2;

    if (ar[mid] == target) //타겟이 가운데 위치
        return mid; //바로 반환
    else if (target < ar[mid]) //가운데 데이터 보다 작으면 
        return BSearchRecur(ar, first, mid - 1, target); //앞부분 이진 탐색
    else //더 크면
        return BSearchRecur(ar, mid + 1, last, target); //뒷부분 이진 탐색
}