[Java] Linear Search AND Binary Search

이번 글에서는 검색 알고리즘의 기초를 이해하기에 핵심적인 두 가지 기본 알고리즘 선형 탐색( Linear Search)와 이진 탐색(Binary Search)에 대해 써볼 예정이다.

사실 여기서 더 들어가면 나오는 트리 구조에 대해 대학원을 준비하면서 어렴풋이 봤던 기억은 있지만, 막상 공부를 위해 세세히 공부하기 시작하니 기초 이론부터 제대로 잡지 않으면 뒤에서 큰일 날 것 같아 글을 쓴다

 

Linear Search

선형 탐색(Linear Search)이란 무엇인가?

선형탐색이란 주어진 배열 리스트(Array List)에서 특정 값을 목표로 i = 0부터, i = n - 1 (혹은 i = 1 부터 i = n까지) 차례대로 검색하는 알고리즘을 말한다.

이러한 알고리즘의 문제는 차례대로 검색하기 때문에 정렬(sort)되어 있지 않은 배열(Array)에 대하여 효율적일 순 있으나, i = 0 부터 i = n - 1까지 차례대로 검색해야 하기 때문에 원하는 데이터 값이 n - 1번 배열에 존재 할 경우 worst case로 모든 데이터와 순차적으로 비교를 해야하기 때문에 배열의 길이가 길어질수록 소요시간이 확연하게 늘어난다.

소요 시간 등의 알고리즘의 효율성을 평가하는 시간 복잡도(Time Complexity) 또는 빅오 표기법(Big O Notation)에선 선형 탐색에 대해 다음과 같이 시간 복잡도를 나타낸다.

 

Worst Case : O(n) (목표값이 n-1번째 항에 존재 할 경우)

 

Best Case : O(1) (목표값이 0번째 항에 존재 할 경우 / constant time을 갖는 알고리즘이라고도 함 )

 

Avg Case : O(n)

시간 복잡도 그래프

 

선형 탐색(Linear Search)의 순서는 다음과 같이 정리 할 수 있다.

 

1. 입력 받기 : 검색할 데이터가 포함된 배열과 찾고자 하는 값에 대하여 입력을 받는다.

 

2. 초기화 : 검색 시작 인덱스를 i = 0( 혹은  i = 1로 ) 설정한다.

 

3. 검색 : 시작 인덱스에 위치한 값과 찾고자 하는 값을 비교한다

1.  만약 목표 하는 값과 일치하면 해당 인덱스를 반환하고 알고리즘을 종료한다.
2.  만약 목표 하는 값과 일치하지 않으면 다음 인덱스로 넘어간다.

이를 기반으로 예시를 들어 설명해보겠다

출처 - https://www.geeksforgeeks.org/

우선 검색할 배열과 목표값을 설정하고,  i = 0으로 설정한 뒤 첫번째 인덱스와 비교를 한다.

다음 이미지의 경우 목표값은 30으로 설정했고, 첫번째 인덱스의 경우 값을 10으로 갖고 있기 때문에 3 - 2의 순서를 이행한다

출처 - https://www.geeksforgeeks.org/

i = 1 번째 인덱스로 넘어가 목표 값인 30과 비교하며 50과 일치하지 않으니 다음 인덱스로 넘어간다

출처 - https://www.geeksforgeeks.org/

i = 2 번째 인덱스로 넘어가게 되면 목표값인 30과 i = 2 번째 인덱스와 값이 일치하게 되면 더이상 다음 인덱스로 이동하지 않고 알고리즘을 종료하게 된다.

---

Binary Search

이분 탐색(Binary Search)란 무엇인가?

이분 탐색이란 이분검색으로도 일컬어지며, 반으로 나누어 연산한다는 것이 특징이다. 

이분 탐색은 배열이 정렬되어 있다는 가정하에 진행 할 수 있는 알고리즘으로, 지정한 배열의 중간지점부터 원하는 데이터 방향으로 2등분을 하면서 진행하기 때문에 같은 데이터 값을 찾을 때에 선형검색보다 소요시간이 적게 걸린다는 장점이 존재하나, 배열이 정렬되어 있을 경우에만 사용할 수 있다는 단점이 존재한다.

이러한 이분 탐색의 시간 복잡도는 O(log n)를 갖게 된다.

 

시간 복잡도 그래프

다음의 예시를 보면 목표 값을 23으로 두고 있고 이분 탐색 알고리즘을 사용해 값을 찾을 것이다.

이분 탐색을 사용 할 수 있게 배열을 값이 커지도록 배열이 정리되어 있다.

 

이분 탐색(Binary Search)의 순서는 다음과 같이 정리 할 수 있다.

 

1. 입력 받기 : 검색할 데이터가 포함된 배열과 찾고자 하는 값에 대하여 입력을 받는다.

 

2. 초기화 :

• 좌측 인덱스 : low = 0(배열의 시작 인덱스)
• 우측 인덱스 : high = n - 1 (배열의 마지막 인덱스)

3. 반복 :

• 중간 인덱스 계산 :

• 값 비교 :
  • 중간 값이 찾는 값과 같으면 알고리즘을 종료한다
  • 중간 값이 찾는 값보다 작으면 검색 범위를 오른쪽 절반으로 좁힌다
  • 중간 값이 찾는 값보다 크면 검색 범위를 왼쪽 절반으로 좁힌다

이를 기반으로 예시를 들어 설명해보겠다

출처 - https://www.geeksforgeeks.org/

우선 검색할 배열과 목표값을 설정하고,  중간 인덱스를 설정한다

출처 - https://www.geeksforgeeks.org/

다음의 경우 총 10개의 배열이므로 5번째 인덱스(16)부터 이분 탐색을 시작한다

목표값은 23이므로 중간 인덱스인 16보다 크므로 오른쪽 절반만 탐색한다

출처 - https://www.geeksforgeeks.org/

오른쪽 절반을 기준으로 다시 중간 인덱스를 찾고 총 5개 이므로 3번째 인덱스(56)부터 이분 탐색을 시작한다

목표값이 23이므로 중간 인덱스인 56보다 크므로 왼쪽 절반만 탐색한다

출처 - https://www.geeksforgeeks.org/

 

왼쪽 절반에서 이분 탐색을 시작하면 값이 23으로 목표값과 일치하고 3번의 단계만에 목표값에 도달했다.

만약 같은 문제를 선형탐색으로 했다면, 6번의 단계를 거쳐 목표값에 도달했을 것이다. (배열의 크기가 더 컸다면 확연한 차이를 보일 것 이다)

 

 

마무리

선형탐색과 이분탐색까지는 생각보다 기계 공학을 전공하면서 수학적 배경의 지식이 알게 모르게 쌓여있다 보니, 이해하기에 부담이 심하지는 않았으나, 이분탐색에서 이어지는 이분탐색트리와 그 안에서의 AVL 트리, 레드 - 블랙 트리 등에 대해서는.. 많이 어려울 것 같다는 느낌이 든다