이진 검색
ko.khanacademy.org
*이 글은 위 링크의 글을 개인공부를 위해 필사 및 정리한 글입니다.
이진검색
이진검색은 정렬된 리스트 중에서 원하는 항목을 찾기에 효율적이다. 탐색 방법은 원하는 항목을 찾을 때까지 리스트를 반으로 접고 이 과정을 반복한다.
이진검색을 많이 사용하는 경우
구체적으로 이진검색을 사용하는 경우는 배열에서 어떤 항목을 찾아야 할 때이다.
예를 들면 티코-2 항성의 목록에는 우리 은하계에서 가장 밝은 별 2,539,913개의 정보를 담고 있습니다. 만약 여기서 별의 이름을 검색하여 항성 목록 중 어떤 별을 찾고 싶다면 어떡해야할까. 만약 선형 검색(linear search)를 이용하면 최악의 경우 2,539,913번의 경우를 모두 찾아야할지도 모른다.
(이하 존대) 하지만 이진 검색(binary search)를 사용한다면, 알파벳 순으로 정렬되어 있다는 전제 하에 최악의 경우 22개의 별만 탐색하면 됩니다.
이진 검색 어떻게 묘사할까
이진 검색 반짜르고... 반짜르고... 반짜르면... 답이 나온다라고 이해할 수 있습니다. 물론 이렇게 직관적으로 사람들끼리는 설명하긴 쉽습니다. 사람들은 그 사이에 생략된 다양한 내용들을 직관적으로 다 알아내기 때문입니다.
하지만 프로그래밍 언어로 알고리즘을 구현하려면 이러한 생략을 최소화해야합니다. 컴퓨터는 직관적으로 생략된 정보를 찾아내지 못하기 때문입니다. 때문에 우리는 알고리즘이 구현되는 순서, 필요한 변수 등을 묘사하고 알고있어야합니다. 그래야 프로그래밍 언어로 알고리즘을 구현하기 더욱 쉬워지겠죠.
이진 검색은 위와 같이 최소값과 최대값에서 반을 제하고, 정답값에 가까운 쪽을 나머지로 취하는 과정을 반복합니다. 그럼 이러한 추측게임에서 이진 검색을 사용하는 방법을 순서대로 알아보겠습니다.
1. min=1, max=n으로 둡니다.
2. max와 min의 평균을 구하고 정수가 되도록 내립합니다.
3. 추측이 맞으면 끝냅니다. 숫자를 찾았네요!
4. 추측값이 작다면 min을 추측값보다 1 크게 설정합니다.
5. 추측값이 너무 크다면 max를 1 작게 설정합니다.
6. 2단계로 돌아갑니다.
이러한 순서에서 중요한 점은 알고리즘의 입력값과 출력값을 분명하게하고, "평균을 구함" "끝냅니다" "돌아갑니다"와 같은 명확한 의미를 전달해야한다는 점입니다.
배열에서 이진 검색 구현하는 방법?
정렬된 배열에서 이진 검색을 어떻게 사용할 수 있을까요.
위 배열에는 25개의 소수가 저장되어 있습니다. 만약 여러분이 73이 소수인지 알고 싶다면 배열에서 73의 위치를 찾아보면 됩니다. 혹은 73 이하의 소수는 총 몇개인지 궁금하다면 여러분은 그저 73의 위치를 구해 그보다 적은 배열의 수를 찾아내기만 하면 됩니다.
어떤 항목의 배열 내 요소를 인덱스라 부릅니다. 인덱스는 0부터 시작하며 하나씩 커집니다.
만약 여러분이 숫자 71을 찾기위해 0번 인덱스에서부터 1번, 2번, 3번 차례대로 찾아가기 시작하면 인덱스 20에서 찾게됩니다. 이러한 순서로 항목을 찾는게 바로 선형 검색입니다.
그럼 이진검색으로도 풀어보겠습니다. 정렬된 리스트로서 이진검색으로도 풀 수 있습니다. 67의 위치를 탐색해보겠습니다.
이진검색의 의사코드(1~6단계의 묘사)를 이용하여 min = 0, max = 24로 설정하면서 시작하겠습니다. 첫번째 추측값은 (min+max)/2인 12번입니다.
12번의 수가 41입니다. 이 배열은 오름차순이며 오른쪽 수가 더 큰 수이기 때문에 41이 67보다 더 작습니다. 그럼 min값을 41의 인덱스인 12+1번으로 바꿔주겠습니다. 그리고 다시 한 번 (min+max)/2를 합니다. 18이 나옵니다. 인덱스 18번을 찾아보면 답은 67입니다. 알고리즘이 끝났습니다.
의사코드, 수도코드(pseudo-code)
위에서 했던 이진검색 방식을 의사코드로 정리하여 표현해봅니다.
여기서 6단계를 보면 2단계로 돌아가야합니다. 그렇다면 과정이 반복되는 것이니 반복문을 사용해야합니다. for문과 while문 무엇을 사용해야할까요.
이진 검색에서 모든 수가 순서대로 커지지 않습니다. 앞서 했던 경우처럼 말입니다. 고로 while문을 선택하는게 더 좋은 선택입니다.
그리고 만약 이진검색에서 원하는 숫자가 배열에서 나오지 않는다면 어떡해야할까요. 이 경우엔 이진검색(binaeary search)이 돌려주어야 하는 인덱스 값을 먼저 결정해야합니다. 이 값은 배열에서 인덱스가 될수없는 수여야합니다. 예를 들어 아무 음수나 가능합니다.
그렇다면 마지막으로 위 의사코드의 복습과 코딩을 해보겠습니다.
복습
using System;
class Program {
static void Main()
{
//25개의 소수
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
//몇번째 수인지 알아오기
var result = DoSearch(primes, 2);
Console.WriteLine("Found prime at index " + result);
//result = 0
}
static int DoSearch(int[] array, int targetValue)
{
int min = 0;
int max = array.Length - 1;
int guess;
while(max > min)
{
guess = (max + min) / 2;
Console.WriteLine(guess);
if(array[guess] == targetValue) { return guess; }
else if (array[guess] < targetValue) { min = guess + 1; }
else { max = guess - 1; }
}
return -1;
}
}의사 코드에 맞게 코드를 짜봤습니다.