[Algorithm] 선형검색, 이진검색 알고리즘과 점근분석(Linear&Binary search)

선형검색, 이진검색 알고리즘이란?

---

Linear&Binary search는 배열에서 특정한 값을 찾을 때 쓰는 검색 방법이다.

해당 글에서는 변수가 N 하나만 있다고 가정하고 작성할 것이다.

 

예를 들어 N = [1, 3, 8, 9, 4, 10, 6, 2] 라는 배열이 있다고 가정하겠다.

이 배열에서 나는 10이라는 값을 찾고 싶다.

 

Linear search는 배열의 앞에서부터 value값이 10인지 아닌지 찾는다.

시간복잡도는 O(n)이다.

시간복잡도가 O(n)인 이유는 만약 내가 2라는 값을 찾고 싶다면 처음부터 끝까지 배열을 순회해야 하기 때문이다.

 

Binary search는 배열의 중간값에서부터 시작한다.

 

우선 Binary search는 배열이 정렬된 경우에만 사용이 가능하다.

N을 오름차순으로 정렬하면 [1, 2, 3, 4, 6, 8, 9, 10]이 될 것이다.

이 경우 전체 index는 7이고 순회의 시작은 7 / 2 = 3.5에서 올림을 해 4번째 index에서부터 검색이 시작된다.

이때 중간값이 찾고자 하는 값보다 큰지 작은지 검사한다.

해당 예시의 경우에는 4번째 index가 6이 될 것이고 찾고자 하는 값은 10이므로 찾고자 하는 값이 중간값보다 큰 것을 알 수 있다.

그리고 3번째 index는 4, 5번째 index는 8이기 때문에 앞의 1, 2, 3, 4 는 깔끔하게 제외하고 오른쪽에서부터 검색을 시작한다.

---

선형검색, 이진검색 알고리즘의 이차함수 그래프 표현과 점근분석

---

그래프

정말 간단하게 Linear search와 Binary search를 그래프로 나타내 보았다.

x축은 배열의 크기(N)를 의미한다.

y축은 비교연산을 몇번 해야 하는가를 의미한다.

 

초록색은 Linear search이다.

y값이 증가함에 따라 선형적으로 비교연산 횟수가 같이 증가하는 것을 볼 수 있다.

 

파란색은 Binary search이다.

Binary search는 N이 증가해도 Linear search에 비해 비교적 연산 증가폭은 낮은 것을 확인할 수 있다.

 

이를 통해 Binary search는 Linear search에 비해 효율적인 알고리즘이다. 라는 것을 알 수 있다.