[알고리즘 공부] 이분 탐색 알고리즘

0. 서론

요즘... 진짜 몸상태가 별로다... 감기 몸살이 홀리몰리하게 3주 넘게 이어지고 있다..

그래도 알고리즘 공부를 안할 수는 없지...

그래서 간단하고 기초적인 알고리즘에 대해 정리하려고 한다.

(컨디션 이슈는 좀 봐조라! ):< )

 

1. 알고리즘 개념

이분 탐색 혹은 이진 탐색은 "정렬되어 있는" 배열에서 특정 값을 빠르게 탐색하는 알고리즘이다.

간단히 말하면 위의 그림처럼 배열을 반으로 나눠가며 특정 값이 있는지 확인하는 방법이다.

 

2. 알고리즘 구조

left(위 사진에서는 low)와 right(위 사진에서는 high)를 기준으로,

중앙 값인 mid 값을 찾은 후

조건에 따라 mid 값보다 크면 다음 left는 mid를 바꾸는 형식으로 반복하는 방법이다.

 

대학에가면 초반에 정렬 알고리즘 이후에 나오는 기본적인 탐색 알고리즘 중에 하나다.

시간 복잡도는 절반씩 나눠가며 찾기 때문에 O(log N) 값이 나온다.

 

3. 알고리즘 구현

다음은 이분 탐색에 대한 간단한 구현이다.

int n = 10; // 배열 크기
int k = 23; // 찾으려는 값

vector<int> arr(n); // 주어진 정렬된 배열(데이터는 이미 들어가 있다고 가정함)

int index = -1;
int left = 0, right = n - 1;

while(left <= right)
{
	int mid = (left + right) / 2;
    
    int value = arr[mid];
    if(value == k) // 값을 찾음
    {
    	index = mid;
        break;
    }
    else if(value < k)	left = mid + 1;
    else				right = mid - 1;
}

 

4. 후기

코딩을 처음 배우고 이 알고리즘을 처음 마주했을 때는 정말 하나도 이해가 안됐는데

어느 정도 코딩 머리가 자라고 나니 정말 기초적인 수준이었다.

그만큼 내가 많이 성장했다는 거겠지...

 

어떤 회사에서는 면접에서 이분 탐색을 손코딩하라고 요구하기도 한다고 한다.

처음 취준했을 때는 이 말이 너무 무서웠는데 이제는 그러지 않아도 될 것 같아서 기분이 살짝 좋아졌다.

 

이제 건강만 되찾으면 좋겠다...

 

5. 참고 사이트

https://www.mathwarehouse.com/programming/gifs/binary-vs-linear-search.php

Binary Vs Linear Search Animated Gifs