이진 검색

이진 검색

• 이진 검색(binary search)은 요소가 오름차순 또순 내림차순으로 정렬된 배열에서 검색하는 알고리즘
• 중앙값을 가지고 비교 후 검색 범위를 반 씩 줄여나가는 방식이다. 그렇기에 배열이 정렬되어 있을 때 사용할 수 있음
• 검색에 필요한 비교 횟수의 평균값은 log n 이다.

public class Test1 {

    public static void main(String[] args) {

        int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12};

        int key = 1; // 찾을 값

        int idx = BinarySearch.binSearch(arr, key);

        System.out.println(arr[idx]);

    }
}

class BinarySearch {

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

        int n = arr.length;

        int pl = 0; // 검색 범위 첫 인덱스

        int pr = n -1; // 검색 범위 마지막 인덱스

        int cnt = 0; // 검색 횟수

        do {
            cnt++;
            int pc = (pl + pr) / 2; // 중앙값의 인덱스
            if(arr[pc] == key) {
                System.out.println("검색 횟수 : " + cnt);
                return pc; // 찾으면 return
            }
            else if(arr[pc] < key)
                pl = pc + 1; // 검색 범위 좁히기;
                // key가 현재 선택한 값보다 크면 검색 범위 첫 인덱스를 선택한 수 바로 뒤로 옮긴다.

            else
                pr = pc - 1; // 검색 범위 좁히기
                // key가 현재 선택한 값보다 작으면 검색 범위 마지막 인덱스를 선택한 수 바로 앞으로 옮긴다.

        } while (pl <= pr); // 검색 범위 첫 인덱스가 마지막 인덱스보다는 같거나 작아야 함

        System.out.println("검색 횟수 : " + cnt);
        return -1;
    }

      // for문 이용
        static int binSearchWithFor(int[] arr, int key) {

        int n = arr.length;

        int pl = 0; // 검색 범위 첫 인덱스

        int pr = n - 1; // 검색 범위 마지막 인덱스

        int cnt = 0; // 검색 횟수

        for(pl = 0; pl <= pr; cnt++) {

            //cnt++;
            int pc = (pl + pr) / 2; // 중앙값의 인덱스
            if(arr[pc] == key) {
                System.out.println("검색 횟수 : " + cnt);
                return pc; // 찾으면 return
            }
            else if(arr[pc] < key)
                pl = pc + 1; // 검색 범위 좁히기;
                // key가 현재 선택한 값보다 크면 검색 범위 첫 인덱스를 선택한 수 바로 뒤로 옮긴다.

            else
                pr = pc - 1; // 검색 범위 좁히기
                // key가 현재 선택한 값보다 작으면 검색 범위 마지막 인덱스를 선택한 수 바로 앞으로 옮긴다.

        }

        System.out.println("검색 횟수 : " + cnt);
        return -1;
    }
}

복잡도

• 알고리즘의 성능을 평가하는 기준

1. 시간 복잡도 : 실행에 필요한 시간 평가
2. 공간 복잡도 : 메모리와 파일 용량이 얼마나 필요한가를 평가

연습문제

1. 이진 검색 후에 찾은 값이 첫 번째로 등장하는 인덱스를 찾아서 반환

public class Test1 {

    public static void main(String[] args) {

        int arr[] = {1,2,3,4,5,6,7,11,11,11,11,23,45,67,123,124,125}; 

        int key = 11;

        int idx = findFirstKey(arr2, key2);

        System.out.println(idx);

    }

    static int findFirstKey(int[] arr, int key) {

        int n = arr.length;

        int pl = 0; // 검색 범위 첫 인덱스

        int pr = n - 1; // 검색 범위 마지막 인덱스

        int pc = -1;

        do {
            pc = (pl + pr) / 2; // 중앙값의 인덱스
            if(arr[pc] == key) {

                // 첫번째로 나오는 key의 인덱스 찾기 => 찾은 인덱스의 왼쪽으로 가면서 같은 key인지 확인
                for(int i = pc - 1; i >= 0;i--) {
                    if(arr[i] != key) 
                        return i+1;
                }

            }
            else if(arr[pc] < key)
                pl = pc + 1; // 검색 범위 좁히기;
                // key가 현재 선택한 값보다 크면 검색 범위 첫 인덱스를 선택한 수 바로 뒤로 옮긴다.

            else
                pr = pc - 1; // 검색 범위 좁히기
                // key가 현재 선택한 값보다 작으면 검색 범위 마지막 인덱스를 선택한 수 바로 앞으로 옮긴다.

        } while (pl <= pr); // 검색 범위 첫 인덱스가 마지막 인덱스보다는 같거나 작아야 함

        return -1;
    }
}