이진검색(binary search) Java 구현

이진검색(binary search) Java 구현

이진검색

알고리즘

요소가 오름차순이나 내림차순으로 정렬되어있는 상태에서 진행
중앙부터 시작해서 대소비교하면서 이동

Java에 Arrays.binarySearch 메소드가 있지만 직접 구현해보고 싶어서 해본다

java 구현

Class BinSearch{
    //요솟수가 n인 배열 a에서 key와 같은 요소를 이진검색한다.
    static int binSearch(int[] a, int n, int key){
        int pl =0; //검색 범위 첫 인덱스
        int pr =n-1; // 검색 범위 끝 인덱스

        do{
            int pc= (pl + pr)/2; //센터값
            if(a[pc] == key){ 
                return pac; //검색 성공
            }else if(a[pc] <key){
                pl = pc + 1; //검색범위 뒤쪽 절반으로 좁힘
            }else{
                pr = pc-1 // 검색범위 앞쪽 절반으로 좁힘
            } while(pl <= pr);

            return -1; //검색 실패
    }
}

시간복잡도 O(logN)