(자료구조) 이진탐색(BinarySearch)

1. 개념

이진 탐색은 목표(Target)값 배열을 탐색할때, 탐색의 범위를 절반씩 줄여나가면서 목표값을 찾는다.

다만, 목표값 배열이 정렬되어 있어야 한다는 제약사항이 붙는다.

순차탐색의 경우, N 개의 배열중 Target 을 찾기위해 최대 N 번을 수행해야 하지만, 

이진 탐색의 경우, 목표값을 탐색할때, 최대 log2N번을 수행하여 찾을수 있다.

 

따라서, 탐색을 해야하는 Data 범위가 늘어날수록 이진탐색이 목표값을 찾기위해 더 효율적이다.

(Data가 정렬되어있다면!)

 

2. 이진탐색의 알고리즘 

   Ⅰ.  최초 탐색의 범위를 지정하기 위해 배열의 시작 위치[First]와 마지막 위치[Last] Index를 지정. 

   Ⅱ. 시작위치와 마지막위치의 값을 더한 후, 2로 나눈값을 중앙 값[Mid]으로 지정한다.

   Ⅲ . 배열의 중앙값과 목표값을 대소비교한다.

        Ⅲ-1. 배열의 중앙값이 목표값보다 큰경우 

                목표값은 배열의 중앙보다 작은범위에 있으므로, 마지막위치[Last] 를 현재 중앙값-1 의 위치로 조정한다.

               이후 다시 Ⅱ 부터 다시 반복 한다.

        Ⅲ-2. 배열의 중앙값이 목표값보다 작은경우

                목표값은 배열의 중앙보다 높은범위에 있으므로, 시작위치[First] 를 현재 중앙값+1 의 위치로 조정한다.

               이후 다시 Ⅱ 부터 다시 반복 한다.

        Ⅲ-3. 배열의 중앙값과 목표값이 같은 경우 

                타겟값을 찾았으므로 해당 인덱스 혹은 목표값을 반환한다.

 

※ 탐색은 언제까지 시행되는가?

탐색이 종료되는 시점은 배열내에서 목표된 값을 찾지 못했을때까지 반복해야한다.

즉, 탐색의 범위가 First 가 Last 의 위치보다 클때까지 반복되어야한다.

(First == Last 가 같은 경우, 탐색을 해야하는 범위가 1개 남았다는 뜻이다.)

 

3. 코드구현(JAVA 구현)

아래와 같이, 배열에 Integer(정수형) 숫자들을 무작위로 입력 받되, 숫자들을 자동으로 정렬(sorting)한 후, 

목표하는 Target Number 를 입력 받고 Target Number가 있는 경우, 해당 배열의 인덱스를 반환

없는 경우 -1을 반환하도록 구현하였다.

    // 1.배열에 Integer 를 입력 받음. (만약 입력받은 숫자의 대소가 무작위인 경우, 자동으로 정렬한다.)

    // 2.입력받은 숫자를 정렬하여, 출력한다.

    // 3.Taget (찾을 숫자)Number 를 입력 받고 해당 숫자가 출력한 숫자순서의 몇번째 인덱스인지를 출력한다.

    // 4. Taget Number 가 없는 경우, -1 을 반환

    // ※ Arrays.sort() 로 정렬

 

<main> 

    public static void main(String[] args)throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("divide" + 1/2);

        System.out.print("Input Array Number: ");

        // Input Arr  

        String [] arrStr = br.readLine().split(" ");

        int arr [] = new int[arrStr.length];

        for(int i=0;i<arrStr.length;i++){

            arr[i] = Integer.parseInt(arrStr[i]);

        }

        // Sorting

        Arrays.sort(arr);

        System.out.print("Input Array(sort): ");

        for(int i=0;i<arr.length;i++){

            System.out.print(arr[i]+" ");

        }

        System.out.println("");

        // Input TargetNumber

        System.out.print("Input Target Number: ");

        int tgtNumber = Integer.parseInt(br.readLine());

        //Output

        System.out.println("Your Target Index is "+binSearch(arr,tgtNumber));

    }

 

<method>

    // Implementation

    static int binSearch(int [] arr, int target){

        int first = 0;

        int last = arr.length-1;

        // Last가 First 보다 크거나 같은 경우, 반복

        while(first<=last){

            // 중앙값을 찾는다.

            int mid = (first + last)/2;

            if(arr[mid]==target){ // 중앙값과 목표값이 일치하는 경우

                return mid;

            }else{

                if(target>arr[mid]){ // 목표값이 중앙값보다 큰 경우

                    first = mid+1;

                }

                if(target<arr[mid]){ // 목표값이 중앙값보다 작은 경우

                    last = mid-1;

                }

            }

        }

        // 목표값을 찾지 못한 경우

        return -1;

    }