1장 자료구조와 알고리즘의 이해 - 이진 탐색 알고리즘 -

1. 이진 탐색 알고리즘이란?

 1) 조건 : 정렬이 되어있어야 한다. 단, 정렬의 조건은 상관없다. 기준이 있으면 된다.

 2) 방법

    i. 시작과 끝의 인덱스 값을 더하여 2로 나눈 뒤, 나온 값의 인덱스에 저장 된 값을 확인

   ii. 확인 한 뒤 맞으면 종료, 원하는 값보다 크냐 작으냐로 중앙 인덱스 값에 + 또는 -를 한다.

  iii. 찾을 때까지 ii를 반복.

2. 이진 탐색 알고리즘의 구현.

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; // 왜 -1을 하였을까?
         else
            first = mid+1; // 왜 +1을 하였을까?
      }
   }
   return -1; // 찾지 못했을 때 반홖되는 값 -1
}

3. 이진 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우(Worst Case)

 

 T(n) = log2n+1 이지만, 빅오 적 관점에선 log2n이 된다.