02. 이진 검색(Binary Search)

* 정의

: 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

 배열의 중간에 위치한 키의 값과 검색할 키의 값을 비교해나가는 알고리즘

 

ex) 배열 a = {0,1,2,3,4,5,6,7,8,9,10}

    검색할 key 값 : 4

 

    1단계 : a[0~10]에서의 중간인 a[5]의 key와 검색할 key의 크기 비교

              => a[5]>검색할 key

    2단계 : a[0~4]에서의 중간인 a[2]의 key와 검색할 key의 크기 비교

              => a[2]<검색할 key

    ~~~이런식으로 값을 찾을 때 까지 반복

 

* 예외 처리

: 값이 없을 경우

 

* java로 구현한 코드

public class example_1 {

    static int binarySearch(int[] a, int n, int key){
        int pl = 0;
        int pr = n-1;
        int result = -1;

        while(pl<=pr){
            int t = (pl+pr)/2;
            if(a[t] == key){
                result = t;
                break;
            }else if(a[t]<key){
                pl = t+1;
            } else {
                pr = t-1;
            }
        }
        return result;
    }
}

 

* API

: static int binarySearch(Object[] a, Object key)

- 검색에 성공한 경우 : 해당 인덱스 반환

- 검색에 실패한 경우 : {(해당 key 값보다 크고 가장 가까운 key값을 가진 인덱스) + 1} * (-1)의 값을 반환