[자료구조와 함께 배우는 알고리즘 입문] 3. 검색 알고리즘(2)

3. 이진 검색

 

3-1. 이진 검색 알아보기

이진검색은 배열이 오름차순이나 내림차순으로 정렬되어있을 때 데이터를 찾기 위해 사용하는 알고리즘이다.

배열이 오름차순으로 정렬되어있는 경우에는 다음과 같이 데이터를 찾으면 된다.

1) 배열의 중앙값과 찾고자 하는 데이터 비교
2) 중앙값보다 데이터가 작으면 중앙값 이전 부분에서 검색 수행
3) 중앙값보다 데이터가 크면 중앙값 이후 부분에서 검색 수행

배열이 내림차순일 경우에는 중앙값과 비교하는 부분은 동일하게 수행하고, 남은 두 단계는 반대로 수행해주면 된다.

기존 검색 알고리즘보다 검색 수행 속도가 절반으로 줄기 때문에 시간복잡도는 O(logN)이 된다.

 

오름차순으로 정렬된 배열을 이진검색하는 코드를 작성하면 아래와 같다.

 static int binSearch(int[]arr, int x, int key){
        int first = 0;      //배열의 맨 첫 인덱스값
        int last = x-1;     //배열의 맨 마지막 인덱스값

        
        do{
            int med = (first+last)/2;    //배열의 중앙값의 인덱스 값
            if(arr[med]==key){           //중앙값과 key일치할 경우 중앙값의 인덱스 값 반환 
                return med;
            }else if(arr[med]>key){      //중앙값보다 key값이 작으면
                last = med-1;            //맨 마지막 인덱스값을 중앙인덱스 -1로 설정해 중앙값 이전 부분으로 검색 수행하도록
            }else{                       //중앙값보다 key값이 크면
                first = med+1;           //맨 첫 인덱스값을 중앙인덱스+1로 설정해 중앙값 이후 부분으로 검색 수행하도록
            }
        }while ((first<=last));          //맨 첫 인덱스값이 마지막 인덱스값보다 작은 동안 수행
        
        return -1;                       //key값 배열 내에 없으면 -1반환
    }

 

3-2. Arrays.binarySearch에 의한 이진 검색

 

자바에서 이진검색을 위해 제공하는 메소드로 오름차순으로 정렬된 배열 검색 시 사용한다.

메소드를 직접 작성할 필요가 없고, 배열의 자료형에 관계없이 검색이 가능하다.

사용형식은 int형의 경우 binarySearch(int[] arr, int key)이다.

자료형에 관계없이 사용가능하기 때문에 사용 시 내가 찾을 배열과 데이터의 자료형에 맞게 작성해서 사용해주면 된다.

 

찾고자하는 키값이 배열 내에 있다면 해당 데이터의 인덱스를 반환시킨다.

키 값이 배열 내에 없다면 " - 1 - 삽입포인트"를 반환한다.

조금 더 이해하기 쉽게 설명해보면 아래와 같이 설명할 수 있다.