[자료구조 with Python] 5. 선형 자료 구조 - 배열(3), 선형/이진 검색

 

 

 

 

앞선 포스팅에서 배열에 대해 설명을 할 때, 배열은 서로 연관된 정보를 하나의 이름으로 관리하는 자료구조라는 뉘앙스로 설명했던 적이 있다. 관련있는 자료를 인접한 메모리에 저장하기 때문에 일반적인 변수에 선언하여 값을 저장하는 것보다 훨씬 빠르게 값을 검색하는 것이 가능해진다. 

 

배열에 존재하는 값을 검색하는 가장 기본적인 방법은, 배열의 0번 index부터 순차적으로 비교하면서 같은 값이 있는지 확인하는 것이다. 컴퓨터의 성능이 좋거나 배열의 크기가 그렇게 크지 않다면 나쁘지 않은 방법이나, 역으로 배열의 크기가 무수히 커지거나, 컴퓨터 성능이 그렇게 좋지 않은 경우라면 이런 기본적인 검색 방법으로는 효율성이 떨어질 수 밖에 없다.

 

이러한 이유로, 배열 내에 존재하는 값을 효율적으로 검색하기 위한 몇몇 알고리즘이 개발되었다. 이번 포스팅에서는 기본 검색방법인 선형 검색부터, 배열 내 값이 오름/내림차순으로 정렬되어 있을 때 사용하는 이진 검색에 대해 알아보려 한다.

 

 

 

1. 선형 검색(Sequential Search)

 

선형검색은 배열 내의 값을 검색하는 가장 기본적인 방법으로 . 위에서 언급한 것과 같이, 배열의 처음부터 순차적으로 값을 비교하고, 검색 값과 동일한 경우 값이 존재함을 알려준다. 

 

 

위의 코드를 보면, 0번 index부터 if문의 조건을 만족하는지 확인하는 과정을 거치는데, 위의 예시처럼 검색값을 배열의 가장 마지막에 위치한 값으로 지정하는 경우, if 문을 25번이나 반복해야 한다. 즉, 선형 검색 코드는 최소 1번에서 최대 n번(배열의 크기)만큼 실행되며 BigO 표기로는 O(n)이 된다. 

 

따라서, 배열의 크기가 커지면 커질수록, 그리고 찾는 값이 배열의 끝에 존재할수록, 코드의 실행 시간은 비례하여 증가할 수 밖에 없다. 

 

 

 

* 보초법(Sentinel Method)

 

선형 검색 알고리즘을 코딩하면 루프(for, while문 등)를 벗어나기 위한 조건 두 가지가 들어가 있어야 한다. 하나는 검색값이 배열 내에 존재할 때, 그리고 다른 하나는 검색 절차가 배열의 마지막 위치에 다다랐을 때다. 따라서 선형 검색은 필연적으로 최소 두 개의 if 조건문을 가지게 된다.

 

 

따라서 선형 검색 코드를 작성할 경우,  검색값을 찾는 if 문과 index가 list 범위를 넘어가는 조건을 확인하는 if문을 거쳐야 한다는 것이다. 별도로 구분된 조건문을 2개나 거치는 코드 자체도 효율적이지도 못한데, 그 와중에 index의 범위를 확인하는 조건문은 거의 사용이 되지도 않기 때문에 코드 효율이 좋지 않을 수 밖에 없다. 

 

따라서, 'index 범위 확인 조건'을 '검색값을 찾는 조건문' 안에 넣어 코드를 작성한다면 기존의 코드보다 효율성 높은 코드를 작성할 수 있다. 이러한 코딩 방법을 보초법(Sentinel Method)이라고 한다. 

 

보초법은 검색하고자 하는 값을 배열의 가장 마지막에 추가한 뒤, 검색을 진행하는 방법이다. 배열의 마지막에 검색할 값이 추가되기 때문에 검색값을 찾는 조건문만 존재하더라도 while문을 벗어나는데에는 문제가 없다. 대신 검색값을 발견하는 위치가 배열의 마지막인 경우, 검색값이 없다는 문구를 출력해주면 된다.

 

 

보초법의 경우, 배열의 마지막에 값을 추가한다는 특징때문에, 기존의 배열과 별도로 임시 배열을 하나 생성해주어야 한다. 따라서 선형 검색 함수에 기존의 배열을 인식할 수 있도록 인자를 추가해주어야 한다. 

 

 

2. 이진 검색 (Binary Search)

 

이진 검색은 오름차순 또는 내림차순으로 정렬되어 있는 값이 저장되어 있는 배열에서 가장 효율적으로 검색을 진행할 수 있는 알고리즘이다. 이진 검색은 술자리 게임 중 하나인 UpDown  - UpDown 게임은 소주 병뚜껑에 적힌 숫자를 찾기(술을 마시기) 위해 임의의 숫자를 말하고, 그 숫자가 병뚜껑의 숫자보다 큰지 작은지 비교하며 범위를 좁혀나가 병뚜껑 숫자를 맞추는 게임이다 - 과 매우 비슷하다. 다만, UpDown과 달리, 값을 기준으로 두는 것이 아니라 배열의 index 값을 기준으로 검색값을 찾아나간다.

 

임의의 배열이 오름차순으로 정렬되어 있다고 가정하자. 만약, 배열의 크기가 n이라면, 가장 처음 검색값을 찾는 위치는 n/2 index가 된다. 만약 n/2 자리의 값이 찾는 값보다. 크다면, 다음으로 찾는 값은 n/2 자리 우측 배열 범위 중 가운데 index가 된다. 반면, 검색값보다 n/2 자리의 값이 작다면 좌측의 배열 중 가운데 index에 위치한 값과 비교하게 된다. 이 과정을 반복하면 검색값이 위치하는 배열의 범위가 점진적으로 좁혀지게 되며, 배열에 값이 존재하는 경우 그 값이 위치한 index를 반환하게 된다. 없으면 그대로 종료되고...

 

오름차순 또는 내림차순으로 정렬된 배열에서, 값을 검색하는 방법의 효율성은 이진 검색 방법이 선형 검색보다 높다고 앞에서 언급했는데, 이를 그림으로도 확인이 가능하다. 1부터 5까지의 숫자가 순차적으로 적혀있는 배열이 있다고 가정하자. 그리고 이들 중 하나인 값인 4을 검색한다고 가정하자. 기본 검색 방법인 순차검색으로 8을 검색한다면 검색값과 일치하는 index를 찾기 위해 조건문을 4번이나 돌려야 한다.

 

 

이진 검색은 어떨까? 아래의 그림을 보자. 위와 동일하게 값은 4를 찾는다.

 

 

선형 검색과는 달리 이진 검색은 검색 값을 찾기위한 조건문을 단 2번만 돌리면 된다.

 

이진 검색을 위한 코드 작성 시 주요하게 생각해야 하는 부분이 두 가지가 있다. 첫 번째는 배열의 시작과 끝, 그리고 중간 위치를 지정하는 것이며, 두 번째는 다음 검색 범위에서 배열의 시작, 끝, 중간 위치를 재정의하는 작업이다. 이를 고려하여 이진 검색 코드를 작성하면 아래와 같은 모양이 된다.

 

 

검색 범위를 다시 재정의하기 위한 배열의 위치 지정에서 가장 중요한 역할을 하는 것이 바로 p_middle 이다. 만약 p_middle에 위치한 값이 검색값과 일치하지 않으면, p_middle index를 기점으로 좌측 또는 우측의 배열로 검색 범위가 한정되기 때문이다. 이 코드를 작성할 때 주의해야 할 점은, p_middle 값이 절대 p_start나 p_end로 바로 대입되면 안된다는 것이다. 어차피 p_middle에 위치한 값은 list_test[p_middle] == value에 의해 검증이 끝난 값이기 때문에, p_start나 p_end로 바로 대입되는 경우, 다음 검색 범위를 의도치 않게 늘리는 우를 범하게 되는 것이기 때문이다.

 

또한 검색에 사용되는 코드가 배열에서의 검색 범위를 좁히는 중에도 반복적으로 사용이 되고 있는데, 이 때문에 while 문에 조건을 달아 코드를 작성한다. while의 조건도 의외로 간단하다. 최종적으로 검색값이 나올 수 있는 조건은 p_start가 p_end 값보다 작거나 같은 경우만 존재하기 때문에 p_start > p_end일 경우, while 문을 벗어나게 만들면 된다.

 

 

 

선형 검색에서는 값을 검색하는 효율을 BigO로 표기하면 O(n)으로 나타낼 수 있다. 이 말은 배열의 크기가 n이라면 최대 n번의 검색 과정을 거쳐야 원하는 값을 찾을 수 있다는 이야기다. 이진 검색의 Big O는 어떻게 표기될까? 위의 예시를 통해 Big O를 구해보도록 하자.

 

가장 처음 진행되는 과정은 중간 위치를 찾고, 중간 위치의 값에 따라 우측 또는 좌측의 배열을 선택하는 과정이다. 만약 중간값이 검색값과 일치하지 않는다면, 검색값은 n/2 크기의 배열 안에 존재할 가능성이 높아지게 된다. 두 번째로 선택한 범위에서의 중간값도 검색값과 일치하지 않는다면, 검색값은 n/4크기의 배열 안에 존재할 가능성이 높아지게 된다. 이 과정을 반복하다보면, n / (2^k) 크기의 배열 안에 검색 값이 존재할 가능성이 높아지게 된다. 

 

k 값이 무한정으로 커진다면 결국 n / (2^k) 값은 1개의 배열만 바라보게 되므로, n / (2^k) = 1 이 된다. 이 값을 다시 정리하면 n = 2^k가 되고, k = log2,n이 된다. 정리하자면 이진 검색으로 배열 안의 값을 검색하게 될 경우, 최대 k 번 만큼 검색을 진행해야 한다는 것이다. 위의 예시에 적용하면 k 값이 2를 조금 초과하는 값이므로, BigO 표기법이 O(log n)임이 증명된다.

 

*  log2,n을 아랫지수인 2는 생략하고 간략히 log n으로 표기한다. 

 

로그가 적용된 n 값은 일반 n 값보다 클 수 없기 때문에( log n < n ), 이진 검색이 선형 검색에 비해 효율이 높음을 알 수 있다.

 

 

위의 사진은 10개의 원소로 구성된 list에서 특정 값을 찾기 위해 bin_search 함수가 몇 번이나 사용되었는지, 그리고 어떤 index들을 참조했는지 확인한 결과이다. BigO 표기법에 의하면 이진 검색은 O(log n)을 따르기 때문에 값을 찾기 위해 해당 함수를 최대 log 10만큼 수행해주어야 한다. 이는 대략 3.x로 4번 이하로 함수가 실행됨을 유추할 수 있으며, 이는 위의 결과 사진과 동일함을 알 수 있다.

 

 

단, 이진 검색은 오름차순이나 내림차순으로 정렬된 배열에서만 사용이 가능하며, 그렇지 않은 배열에서는 이진 검색 알고리즘으로 정확한 검색을 진행할 수 없게 된다(배열의 정렬에 대해서는 추후 포스팅 할 예정이다).

 

그럼, 정렬되지 않은 자료에 대해서 선형 검색보다 더 효율적으로 검색할 수 있는 알고리즘은 존재하지 않을까? 다행히 인류의 발전을 위해 노력한 많은 분들에 의해 선형 검색으로 인한 시간 낭비를 줄일 수 있는 알고리즘이 개발되었다.

 

다음 포스팅에서는 또다른 검색 알고리즘인 Hash 검색에 대해 알아보려 한다.

 

 

 

Fin.