검색 (4) - 이진 검색 (Binary Search)

1. 알고리즘 개요

• 검색을 O(logN)만에 수행할 수 있는 검색 알고리즘

• 데이터가 미리 정렬되어있어야함.

• 데이터를 절반으로 잘라서 중앙이라면 값을 리턴하고, 아니면 앞뒤로 절반씩 탐색 범위를 좁힘.

• 아래 예시는 '37'을 찾는 과정으로 Sequential Search에 대비해 매우 빠른 속도를 보임.

 

 

 

• 삽입 : 자료집합에서 알맞은 위치에 삽입 (삽입정렬의 inner loop와 동일) : O(N)

• 삭제 : 원소를 찾아서 지우고, 뒤의 원소들을 앞으로 당김 : O(N)

• 검색 : 원소를 찾아서 반환 : O(logN) (한번 재귀할때 마다 연산이 절반으로 줄어듬)

 

3. 소스코드

import java.util.Arrays;

public class BinaryMap {
    private Integer[] array;
    private int capacity;
    private int count = 0;

    public BinaryMap(int capacity) {
        this.capacity = capacity;
        this.array = new Integer[capacity];
    }

    public Integer get(int val) {
        return binarySearch(array, val, 0, count - 1);
    }

    private Integer binarySearch(Integer[] arr, int val, int l, int r) {
    // 이진탐색 메소드
    
        if (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] == val) // 중앙값과 같다면 리턴 
            	return arr[mid];
            
            if (arr[mid] < val) // 중앙값보다 크다면 오른쪽에서
            	return binarySearch(arr, val, mid + 1, r);
            else // 중앙값보다 작다면 왼쪽에서 이진탐색 재귀호출
            	return binarySearch(arr, val, 0, mid - 1);
        } else 
        	return null;
    }

    public boolean put(int val) {
        if (capacity > count) {
            if (count == 0) array[count] = val;
            else putWithInsertionSort(val);

            count++;
            return true;
        }
        return false;
    }

    private void putWithInsertionSort(int val) {
    // 입력데이터를 정해진 위치에 삽입함
    
        int i = count - 1;
        for (; i >= 0 && val < array[i]; i--) {
            array[i + 1] = array[i];
        }
        array[i + 1] = val;
    }

    public boolean remove(int val) {
    // 데이터가 정렬되어있기 때문에 삭제시에는 신경쓰지 않아도 됨
    // 때문에 ArraySeqMap과 동일한 방법으로 삭제함
    
        int indexToRemove = -1;
        for (int i = 0; i < count; i++) {
            if (array[i] == val) {
                indexToRemove = i;
            }
        }

        if (indexToRemove != -1) {
            for (int i = indexToRemove; i < count; i++) {
                if (i == capacity - 1) {
                    array[i] = null;
                } else {
                    array[i] = array[i + 1];
                }
            }

            count--;
            return true;
        }
        return false;
    }

    public void check() {
        System.out.println(Arrays.toString(array));
    }
}

 

4. Reference