검색 알고리즘(2)-이진검색

📖이전글

검색 알고리즘(1)-선형검색

 

 

목차

 

이진검색

일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행하는 알고리즘이다. 전제 조건은 요소가 오름차순 또는 내림차순으로 정렬되어 있어야 한다.

 

 

1. 키 값은 21이다.
2. 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 가운데 인덱스를 pc 라고 한다. 
3. 제일 가운데 요소인 a[3] 부터 검사한다.
4. 검색하려는 값 21은 a[3] 값인 10보다 크다. 때문에 왼쪽의 값들은 제외한다.
5. 그 다음 a[4]~a[6] 의 가운데 요소인 a[5] 를 검사한다.
6. 21은 a[5] 값인 22보다 작기 때문에 오른쪽의 값들은 제외한다.
7. a[4] 값인 21을 찾고 검색 종료.

여기서 중요한 것은, 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 거의 반으로 좁혀진다는 것이다.

구현을 할 때에는 한 단계씩 진행할 때 마다 pl값, pr값, pc값을 업데이트 해주어야 한다.

 

이진 검색 종료 조건

1. a[pc]와 key가 일치하는 경우
2. 검색 범위가 더 이상 없는 경우

이진 검색 구현

    //요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색한다.
    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 pc; //검색 성공
            }else if(a[pc]<key){
                pl = pc + 1; //검색 범위를 뒤쪽 절반으로 좁힘
            }else{
                pr = pc - 1; //검색 범위를 앞쪽 절반으로 좁힘
            }
        }while(pl <= pr);
        
        return -1; //검색 실패
    }

 

Arrays.binarySearch 에 의한 이진 검색

자바에서는 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다. 이진 검색 메서드를 직접 코딩할 필요가 없고 모든 자료형 배열에서 검색할 수 있다.

 

---

참고

자료구조와 함께 배우는 알고리즘 입문