[알고리즘] 이진 탐색

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다.

---

정렬된 배열

정렬된 배열은 값이 항상 순서대로 있어야 한다는 점이다.

즉, 값을 추가할 때마다 적절한 셀에 넣어 배열의 값을 정렬된 상태로 유지한다.

 

이렇게 3, 17, 50, 202로 정렬된 배열이 있다고 가정할 때,

 

정렬된 배열에서는 값을 오름차순으로 유지하려면 적절한 위치에 75를 삽입해야 한다.

 

하지만 이는 말처럼 쉽지가 않다.

컴퓨터는 75를 올바른 위치에 바로 넣는 작업을 한 단계로 처리할 수 없다.

 

먼저 75가 들어갈 올바른 위치를 찾아야 하고, 이후 다른 값들을 옮겨 빈 공간을 만들어야 한다.

 

처음의 배열 상태로 돌아가보자.

 

1. 인덱스 0의 값을 확인해서 삽입하려는 값인 75가 왼쪽으로 들어갈지, 오른쪽으로 들어갈지 정한다.
75는 3보다 크므로 적절한 위치가 아니다.

 

2. 다음 셀의 값을 확인한다.
75는 17보다 크므로 적잘한 위치가 아니다.

 

3. 다음 셀의 값을 확인한다.
75는 80보다 작으므로 적절한 위치이다.
하지만 75를 이 위치에 넣으려면 데이터를 옮겨야 한다.

 

4. 마지막 값을 오른쪽으로 옮긴다.

 

5. 마지막 앞에 있던 값을 오른쪽으로 옮긴다.

 

6. 75를 올바른 위치에 삽입한다.

 

위 예제에서 최초에 원소가 4개였고, 삽입에 6단계가 걸렸다.

정렬된 배열에 원소가 N개이면, 삽입에 총 N + 2단계가 걸린다고 말할 수 있다.

삽입할 값이 가장 큰 수라서 배열 맨 끝에 놓이게 된다면, 새 값을 기존의 값과 모두 비교하는 데 N단계가 걸리고 삽입 자체에 1단계가 걸리니 총 N + 1단계이다.

 

값이 정렬된 배열 앞 부분에 놓여야 한다면 비교가 줄어들고 이동이 늘어난다.
값이 배열 뒷 부분에 놓여야 한다면 이동이 줄어들지만, 되지만 비교가 늘어난다.

 

정렬된 배열 자체는 원소를 삽입할 때는 비효율 적이라고 생각할 수 있으나, 정렬된 배열에서의 검색은 엄청난 성능을 발휘한다.

 

---

 

이진 탐색

원소 9개를 포함하는 정렬된 배열이 있다고 가정하면, 컴퓨터는 각 셀에 어떤 값이 있는지 바로 알 수 없다.

 

정렬된 배열에서 7을 찾는다고 가정하면 아래와 같은 단계로 작동한다.

 

1. 가운데 셀부터 검색을 시작한다.
배열의 길이를 2로 나누어 가운데 셀의 인덱스를 계산하여 접근한다.

값이 9이므로 7은 왼쪽 어딘가에 있다고 판단하게 된다.

따라서 오른쪽의 값은 비교를 할 필요가 없다.

 

2. 9보다 왼쪽에 있는 셀들 중 가운데 값을 확인한다.
가운데 값이 두 개이므로 임의로 왼쪽 값을 선택한다.

이 셀의 값은 4이므로 7은 오른쪽 어딘가에 있어야 한다.

따라서 왼쪽의 셀은 비교하지 않는다.

 

3. 셀이 두 개 남았으므로 임의로 왼쪽에 있는 셀을 선택한다.

 

4. 마지막 남은 셀을 확인한다. 여기에 원하는 값(7)이 없다면 이 배열에는 원하는 값이 없다는 뜻이다.

 

---

 

선형 탐색 VS 이진 탐색

위 이미지는 이진 탐색과 선형 탐색의 차이를 보여준다.

 

100개의 값을 갖는 배열에서 각 검색에 필요한 최대 단계 수는 아래와 같다.

• 선형 검색 : 100단계
• 이진 탐색 : 7단계

이진 탐색을 사용하면 한 단계마다 검색해야 할 셀 중 절반을 제거할 수 있다.

 

다른 관점에서 보면 어떤 패턴이 보인다.

1. 배열의 크기가 3일 때 이진 검색에 필요한 최대 단계 수는 2다.
2. 배열의 크기를 두 배로 늘리면(단순한 계산을 위해 한 칸을 더 추가해서 홀수로 유지하면) 크기가 7이 되고, 이진 검색에 필요한 최대 단계 수는 3이 된다.
3. 배열의 크기를 두 배(그리고 한 칸 더 추가)로 늘리면 크기가 15가 되고 이진 검색에 필요한 최대 단계 수는 4가 된다.

정렬된 배열의 크기를 두 배로 늘릴 때마다 이진 검색에 필요한 단계 수가 1씩 증가하는 패턴이 보인다.

즉, 데이터가 두 배로 늘릴 때마다 이진 검색에서는 필요한 단계가 1씩 증가한다는 뜻이다.

 

선형 검색에서는 데이터가 N배 늘어나면 검색의 단계도 N배 늘어나는 것과는 대조적이다.

원소가 1만 개인 배열에서 선형 검색은 최대 1만 단계가 걸리지만, 이진 검색은 최대 13단계면 충분하다.

 

그렇다고 해서 무조건 이진 검색을 사용해야 하는 것은 아니다.

이진 검색을 사용하려면 정렬된 배열을 만들기 위해 삽입 과정이 일반 배열보다 까다롭다.

따라서 장단점을 정확히 알고 적절히 사용하는 것이 중요하다.