순차 탐색과 이진 탐색 알고리즘

단방향으로 하나씩 탐색하기에 선형 탐색(Linear Search) 알고리즘이라고도 한다.

순차 탐색 알고리즘 구현

---

순차탐색알고리즘

ary[0]부터 ary[n]까지 순차적으로 탐색하여 target값을 찾는 방식이다.

시간 복잡도 계산

---

$T(n)$

빅-오 표기법

---

$T(n)=n ⟹ O(n)$

(Binary Search)

배열에 저장된 정렬된 데이터를 대상으로 적용 가능하다.

반씩 덜어내며 target값과의 비교를 통해 target값을 찾을때 까지 계속해서 반으로 덜어낸다.

이진 탐색 알고리즘 구현

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;
 }

• first는 탐색 대상의 시작 인덱스 값이다. (idx는 0부터)

• len은 탐색 대상 인덱스의 길이이다.
  (sizeof 연산자를 통해 배열 길이를 구한 값을 인수로 받는다.)

• last는 탐색 대상의 마지막 인덱스 값이므로 len-1이다.

• mid값이 target값이 아니면 대소 비교 후 반 으로 줄인다.

시간 복잡도 계산

---

n이 1이 될때까지 2로 나눈 횟수 k회
그리고 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회를 진행해주어야 하므로

T(n) = k+1 이다.

이제 k를 구하면 시간 복잡도가 나오는데

$n \times (\frac{1}{2})^k = 1$
$n \times 2^-k = 1$
$n = 2^k$

양 변에 밑이 2인 log를 취해주면 정리가 된다.

$n = 2^k$
$log_2n = log_22^k$
$log_2n = klog_22$
$log_2n = k$

$T(n) = log_2⁡𝑛$

빅-오 표기법

---

$O(log n)$

(일반적으로 컴퓨터 분야에서 $log n$은 $log_2 n$을 뜻한다.)