이분검색(Binary Search) - Java구현

이분검색은 검색할 범위를 반으로 줄여가며 답을 찾아가는 알고리즘이다.

 

이분검색

말로하면 지루하니까 미천한 그림판실력을 발휘해보겠다.

 

다음과 같이 오름차순으로 정렬된 배열이 있다고 생각해보자.

우리는 여기서 1이 몇번째에 있는지 바로 알 수 있지만 컴퓨터는 그렇지 못하다.

 

이분 검색의 절차를 그려보자면 아래와 같다.

• 배열의 정 가운데 요소를 기준으로 반으로 쪼갠다.
• 1이 가운데의 원소인 9보다 작으면 왼쪽 배열을 선택한다.
• 왼쪽 배열의 가운데 요소 3을 기준으로 쪼갠다
• 1이 가운데 원소인 3보다 작으면 왼쪽배열을 선택한다.
• 1이 남았다. 찾으려는 값이 1이기 때문에 종료한다.

 

이분검색은 분할정복 알고리즘 중 가장 간단한 부류에 속한다. 왜냐면 입력사례를 분할해 해답을 구하고, 결과를 취합할 필요가 없기 때문이다.

 

분할정복으로 재귀 알고리즘을 개발할 때 아래의 사항들을 꼭 고려해야한다!

• 작은 입력사례의 답으로 전체 입력사례의 답을 구하는 방법을 고안
• 더 이상 분할이 불가능한 입력사례를 판단할 종료조건을 정한다.
• 종료조건을 만족하는 경우 답을 어떻게 구하는지 정한다.

내 실습을 위해서 Java로 구현하는 예제를 만들어보겠다.

 

재귀 방식을 이용한 이분 검색

    public static int recursion(int[] arr, int findNumber, int low, int high) {
        if(low > high) return -1; // 마지막까지 갔을 때 찾을수 없다라는 값인 -1 반환
        int mid = low + (high - low) / 2;
        if(arr[mid] == findNumber) {
        	return mid; // 찾는 값일 때 해당 번째 반환
        }
        else if (arr[mid] < findNumber) { // 찾는 값보다 작을 때는 중간값보다 오른쪽에 있음
            return recursion(arr, findNumber, mid + 1, high); 
        }else {
            return recursion(arr, findNumber, low, mid - 1); // 반대로 중간값보다 왼쪽에 있음
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 6, 9, 13, 17, 20, 26};
        int find = 13;
        int result = recursion(arr, find, 0, arr.length - 1);

        System.out.println(find + "은(는) 배열의 " + result + "번째에 있습니다.");
    }

다른 예제로 재귀 방식이 아니라 이분 검색을 구현해보자

public static int binarySearch(int[] arr, int findNumber) {
    int low = 0; // 처음의 항목은 0으로 고정
    int high = arr.length - 1; // 마지막 항목은 arr.length -1 번째에 위치
	
    while(low <= high) {
        int mid = low + (high - low) / 2; // 인덱스의 중간 값
        
        // 중간 값이 찾는 값과 같다면 정답임
        if(arr[mid] == findNumber) {
            return mid;
        }
        // 중간 값이 찾는 값보다 작으면 mid보다 큰 쪽에 위치하게 됨.
        // 반대로 중간 값이 작으면 mid보다 작은 쪽에 위치하게 됨
        if(arr[mid] < findNumber) {
            low = mid + 1;
        }else {
            high = mid - 1;
        }
    }
    return -1;
}

public static void main(String[] args) {
    int[] arr = {1, 3, 6, 9, 13, 17, 20, 26};
    int find = 1;
    int result = binarySearch(arr, find);

    System.out.println(find + "은(는) 배열의 " + result + "번째에 있습니다.");
}

이해하기 어려운 코드는 아닐거라고 생각한다.

 

재귀와 반복문을 통한 이분 검색 공통으로 설명할 수 있는 실행 순서를 그림으로 보자

아래 이미지를 순서대로 보자.

• 처음의 low는 0, mid는 3, high는 7이다
• 찾으려는 값인 1은 9보다 왼쪽에 있기 때문에 high를 앞으로 당겨줘야 한다.
  
  • 코드에서 high를 mid -1 로 하는 이유는 이미 9는 본 값이기 때문에 굳이 9를 또 가진 배열일 필요가 없기 때문이다.
• 위의 행동을 반복하면 결국 mid가 배열의 0번째인 1이 된다.
• 반환한다
• 만약 값이 없으면 -1을 반환한다.

 

이분검색의 시간 복잡도

이분 검색의 시간 복잡도는 O(log n) 이다.

만약 배열의 길이가 32개라면 5번만에 찾을 수 있고,

1024개라면 10번의 식으로 2의 n 제곱마다 1번씩 증가한다.

 

중요!

이분검색은 기본 조건이 정렬된 배열을 가지고 검색해야 한다.