Binary Search(이진탐색)

이진 탐색(Binary Search)이란?

Binary = 이진법(0,1)의, 두 부분으로 이루어진 이란 뜻으로

이진 탐색은 정렬이 된 배열에서 원하는 값을 찾을 때 중앙을 기준으로 두 부분으로 나누어서 탐색해 나가는 방법이다

 

예를 들어 보자면 오름차순으로 정렬된 상자가 7개 있는데, 그 상자에는 각각 다른수의 공이 들어있습니다.

한 직원이 상사의 지시를 받아서 "공 25개 들어있는 상자를 가져와라"라는 명령을 받았습니다.

이 직원이 상자를 가지러 갔는데 운이 없게도 업무담당자가 상자 겉면에 표시를 안해뒀습니다

지시를 받은 직원은 상자가 오름차순으로 순서로 정렬되있는것 밖에 모릅니다

이 직원은 어느 상자를 열어볼까 고민을 합니다(상자가 3중 잠금이 되있어서 효율적으로 열어봐야합니다)

① 첫 생각이 1번상자부터 열까? 하지만 7번 박스가 마지막일수도 있습니다(ㆍㆍㆍㆍ 20 24 25)

② 그렇다면 마지막 7번 상자부터 열까? 하지만 1번박스가 25개 일 확률도 있습니다(25,26,30,45,50ㆍㆍ)

③ 여러 고민을 하다가 직원은 예전에 배웠던 Binary Search가 생각 나서 실행에 옮깁니다

 

실제로 들어있는 갯수를 이러했습니다.

 

직원은 Binary Search 방식대로 중앙에 있는 4번 상자를 열어봅니다

 

상자를 열어보니 800개 군요 그렇다는 것은 뒤에 상자는 800개 이상이니 전부 제외를 시킬수 있습니다

800개를 확인한 직원이 당연히 3번박스는 아니겠지 하는 생각으로 1,2번 상자중 도박을 해서 1번 상자를 열어본다면

시간낭비가 될 수 있겠군요. 하지만 직원은 도박을 하지 않고 Binary Search에 따라서 다음 절차인

2번 상자를 열어봅니다.

2번 상자를 열어본 직원은 2개인것을 확인하고 바로 3번째 상자가 공 25개가 들어 있는 상자라는 걸 알 수 있습니다.

Binary Search에서의 최악의 경우는

     

일때 입니다. 상자가 7개 이므로 7 = 2²<7<2³ , log₂2²이므로 최악의 경우라도 2번안에 찾는 다는 뜻입니다

위 상황에서 뒤에 상자부터 확인했다면 5번을 확인해야 했고, 앞에서 확인했어도 3번은 열어봤어야 했는데

BinarySearch를 사용해서 시간을 절약했습니다.

이처럼 Binary Search는 n이 커질수록 효율성이 올라갑니다.

 

 

이진탐색(Java)

① 배열생성

   배열을 생성한후 잘 들어갔나 확인해보겠습니다

public class Binary 

{

    public static void main(String[] args)

    {

        int i;

        int box[] = {1, 2, 25, 800, 1500, 2000, 9999};

        

        for(i=0;i<=box.length-1;i++)

        {

            System.out.println((i+1)+"번 Box = "+box[i]+"개");

        }

    }

}

 

② 중앙찾기

   위의 배열은 box[0],box[1],box[2],box[3],box[4],box[5],box[6]으로 되있습니다.

   중앙을 찾기 위해서 배열의 처음인 0, 마지막인 6을 더한후에 2로 나누겠습니다

box[3]이 중앙이 되겠군요 = box[3]는 공 800개가 들어있는 4번박스 입니다

만약 상자가 10개라면 0+9/2 = 4.5가 나오는데 이때는 나머지를 버려주고 box[4]를 중앙으로 잡아주시면 됩니다

public class Binary 

{

    public static void main(String[] args)

    {

        int i;

        int box[] = {1, 2, 25, 800, 1500, 2000, 9999};

        int first = 0;

        int last = box.length-1;

        int middle;

        System.out.println("공 25개가 들어있는 Box찾기 시작");

        System.out.println("-----------------------");

        System.out.println("첫번째 도전!!!");    

        middle = (first+last) / 2;    

        System.out.println("중앙은 "+(middle+1)+"번째 상자이므로 열어보자");

    }

}

처음에 확인할때는 First와 Last가 정해져있습니다. box[0]이 처음이고 box[6]이 마지막이겠죠?

 

③ 첫 상자를 한번 열어봤다

public class Binary 

{

    public static void main(String[] args)

    {

        int i;

        int box[] = {1, 2, 25, 800, 1500, 2000, 9999};

        int first = 0;

        int last = box.length-1;

        int middle;

        System.out.println("공 25개가 들어있는 Box찾기 시작");

        System.out.println("-----------------------");

        System.out.println("첫번째 도전!!!");    

        middle = (first+last) / 2;    

        System.out.println("중앙은 "+(middle+1)+"번째 상자이므로 열어보자");

        

        if(box[middle]==25)

        {

            System.out.println("찾았다");

        }

        else if(box[middle]>25)

        {

            System.out.println("틀렸군 "+box[middle]+"개 있었구만.. 하지만 1,2,3번 상자중에 있겠구만");

        }

        else

        {

            System.out.println("틀렸군 하지만 5,6,7번 상자중에 있겠구만");

        }

    }

}

 

이런 식으로 다시 중앙을 찾고 무한루프를 돌리면서 값을 찾으면 될 것 같습니다만!

한가지 조건을 더 넣어야 합니다

위 소스 그대로 무한루프를 돌린다면 굳이 알고있는 상자를 한번더 여는 경우가 생길 수 있습니다.

예를들어 반복해서 중앙상자를 열어보던 중에 열고 난 후에 열어볼 상자가 한개 남았을 경우

* (1,25,30) 이럴경우 25개든 상자를 열어보고 끝낼수 있으나.

① 상자가 전체 7개일경우(1,2,25,800,1500,2000,9999) -> (1,2,25) -> 2개든 상자를 확인후 25개 상자를 한번더 확인

② 상자가 전체 5개일경우(1,25,30,55,100) -> (1,25) -> 1개든 상자를 확인후 -> 25개 상자를 한번더 확인

열어본 후에 경우의수가 1가지 남았을때는 굳이 확인을 안해도 되니 그 조건을 추가시켜서 작성해보겠습니다.

public class Binary 

{

    public static void main(String[] args)

    {

        int i = 0;

        int box[] = {1, 2, 25, 800, 1500, 2000, 9999};

        int first = 0;

        int last = box.length-1;

        int middle;

        int temp;

        System.out.println("공 25개가 들어있는 Box찾기 시작");

        System.out.println("-----------------------");

        

        while(true)

        {

            i++;

            middle = (first+last) / 2;

            

            System.out.println(i+"번째 도전!!!");    

                

            System.out.println("중앙은 "+(middle+1)+"번째 상자이므로 열어보자");

            

            if(box[middle]==25)

            {

                System.out.println("찾았다");

                break;

            }

            else if(box[middle]>25)

            {

                System.out.println("틀렸군 "+(middle+1)+"번 상자에는 "+box[middle]+"개 있었구만");

                last = middle-1;

                temp = middle+1;

            }

            else

            {

                System.out.println("틀렸군 "+(middle+1)+"번 상자에는 "+box[middle]+"개 있었구만");

                first = middle+1;

                temp = middle+1;

            }

            System.out.println("");

            if((last-first)==0)

            {

                if(box[middle]>25)

                {

                    System.out.println("그렇다면 "+(temp-1)+"번째 상자에 있겠군");

                }

                else

                {

                    System.out.println("그렇다면 "+(temp+1)+"번째 상자에 있겠군");

                }    

                break;

            }

        }

    }

}

소스코드를 살펴 보면 

상자를 열었는데 공이 25개이상 있다면 앞부분 상자를 확인해야 하므로 first는 변하지 않는다

그러므로 last만 바꿔준다.

last = middle-1;

상자를 열었는데 공이 25개미만 있다면 뒷부분 상자를 확인해야 하므로 last는 변하지 않는다

그러므로 first만 바꿔준다.

first = middle+1;

상자가 하나 남았을때 확인하지 않고 끝내는 방법을 보면

if((last-first)==0)

            {

                if(box[middle]>25)

                {

                    System.out.println("그렇다면 "+(temp-1)+"번째 상자에 있겠군");

                }

                else

                {

                    System.out.println("그렇다면 "+(temp+1)+"번째 상자에 있겠군");

                }    

                break;

            }

이 부분은 중앙상자를 열고 난 후에 다음 오픈전에 first와 last를 구하는데

만약에 상자가 하나 남았을때는 first와 last가 같아지므로 first-last = 0이 된다. 이때 종료시켜 주면 된다.