이진검색

이진검색이란?

요소(데이터)가 정렬 된 배열일 때 선형검색보다 좀 더 빠르게 검색할 수 있는 알고리즘.

---

---

특징?

1. 검색단계를 한 단계 진행 시마다 검색범위가 대략 절반 가량 줄어든다. ( 시간 복잡도 : O(log n) ) 
-> 선형검색의 경우 첫 번째 요소부터 마지막 요소까지 순차적으로 검색해나가며 원하는 값을 찾아나가기에 정렬이 크게 필요하지는 않다. 그러나 이진검색의 경우 첫 번째 요소가 아닌 검색 범위의 중앙 요소를 기준으로 원하는 값의 대소여부를 파악하며 범위를 대략 절반씩 줄여나간다. 그렇기에 반드시 데이터가 정렬되어 있어야한다.

2. 검색 요소를 한칸 씩 이동하며 검색하는 것이 아닌 범위의 중앙 요소를 검색 대상으로 한다.
-> 검색하는 요소의 위치가 여러 칸으로 이동한다.

---

코드?

public class BinSearch {

    static int binSearch(int[] a, int n, int key){
        int pl = 0; // 검색 범위 맨 앞 인덱스
        int pr = n - 1; // 검색 범위 마지막 인덱스 
                   -> 배열은 0번부터 시작하기에 (배열크기(n) - 1)이 마지막 인덱스 번호이다

        do{
            int pc = (pl + pr) / 2; // 검색 범위 중앙 인덱스
            if(a[pc] == key)
                return pc;
            // 오름차순 정렬이기에 찾고자 하는 값이 현재 검색중인 값보다 클 시 이전 인덱스는 모두 제외대상이다.    
            else if(a[pc] < key)
                pl = pc + 1;
            else
                pr = pc - 1;
         //검색 범위 첫 번 와 마지막인 같아지거나 마지막 검색 범위가 더 작아질 때까지       
        }while(pl <= pr); 
        
        //for문으로 
        for(;pl <= pr;){
            int pc = (pl + pr) / 2;
            if(a[pc] == key)
                return pc;
            else if(a[pc] < key)
                pl = pc + 1;
            else
                pr = pc -1;
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.print("요솟수 : ");
        int num = stdIn.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요.");

        System.out.print("x[0]: ");
        x[0] = stdIn.nextInt();

        for(int i = 1 ; i < num ; i++){
            do {
                System.out.print("x["+i+"]: ");
                x[i] = stdIn.nextInt();
            }while (x[i] < x[i-1]);
        }

        System.out.print("검색할 값: ");
        int key = stdIn.nextInt();

        int idx = binSearch(x,num,key);

        if(idx == -1)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println("그 값은 x["+ idx + "]에 있습니다.");
    }
}

---

자바 Arrays.binarySearch(배열, 찾을 값)을 활용한 이진검색?

자바에서는 배열에서 이진검색을 하는 메서드를 표준 라이브러리로 제공하기에 별도의 메서드를 구현하지 않고도
이진 검색을 할 수 있다.

---

Do it! 자료구조와 함께 배우는 알고리즘 입문 선형 알고리즘 참조

-> overloading을 통하여 다양한 자료형 배열도 이진검색이 가능하다.

---

종료조건 ?

성공 시 : 찾은 위치의 인덱스를 반환한다.

실패 시 : 데이터가 정렬되어 있다는 것을 생각하며 찾고자 하는 데이터가 위치해야 할
인덱스번호를 (- 인덱스 번호 -1) 값으로 반환한다.

EX)
{1,3,5,7,9} 배열이 있을 시 2를 찾고 싶다면 배열에는 실제로 값이 없기에 검색한 값을 찾을 수 없게된다.
이때, 실제로 찾고자하는 값 2는 1,3 중간에 위치해야하며 값을 찾을 수 있기 위해서는
배열 요소들이 {1,2,3 ,~}와같이 배치되어 있어야한다.
이 때, 찾고자 하는 값 2는 1번 인덱스에 위치했어야 하기에, 반환 값은 (-1 - 1) ->  -2가 반환된다.