20180714 BinarySearch : Algorithm

BinarySearch

이분탐색으로 부른다. 바이너리 서치는 배열요소 속에서 특정한 값을 찾기위해 이용하는 알고리즘 중 하나이다. 자바에 기본 내장되어 있는 알고리즘이다.

바이너리 서치는 기본적으로 정렬이 되어있는 상태에서 탐색을 실시한다. 하나의 배열이 있다고 가정하고 이 배열은 11개의 정수형 요소를 가진다.

{1, 3, 4, 5, 13, 20, 25, 40, 42, 44, 53}

여기서 13을 찾는다고 가정한다면, 아래와 같은 절차를 밟아나간다.

(1) 11개의 요소들

(2) (11 / 2) 개의 요소들

(3) (11 / 4) 개의 요소들

(4) (11 / 8) 개의 요소들

...

(n) 1개의 요소 탐색 완료

시간복잡도는 O(logN) 이 걸린다. 

int [] array = new int[]{2, 3, 4, 5, 13, 20, 25, 40, 42, 44, 53};
int searchNumber = 13;
boolean flag = binarySearch(array, 13);
 
public static boolean binarySearch(int[]array, int searchNumber){
    
    // 인덱스로 확인
    int left = 0;
    int right = array.length - 1;
    int mid = 0;
    
    while( left <= right ){
        mid = (left + right) / 2;
        
        // 탐색완료
        if(array[mid] == searchNumber)
            return true;
        
        // 검색숫자가 더 큰 경우
        else if(array[mid] < searchNumber)
            left = mid + 1;
        
        // 검색숫자가 더 작은 경우
        else
            right = mid - 1;
    }
    
    return false;
}

백준에서 다양한 문제를 만나볼 수 있었다. 이분탐색에 대한 문제를 풀면서 느낀거는 문제는 이분탐색이라고 말하지 않는다. 그리고 문제가 이분탐색에 대한 문제를 알고 있다고 하더라도 응용하기가 어려웠다.

이분탐색을 풀면서 생각해야할 부분은 숫자의 범위에 대한 것이다. 특정범위보다 큰 것인지 혹은 작은 것인지 확인해야 하는 문제가 있었다. 그리고 한편으로 느낀 것은 나의 풀이에 대해서 왜 그렇게 푸는지 설명할 줄 알아야 한다는 것. 너무 문제 풀이에 집중한 나머지 그 과정을 도출해내는 것을 중요하게 생각하지 않는 것들도 있어서 조심해야겠다.

공유기 설치

나무자르기

랜선자르기

수 찾기

예산

[ 참고링크 ]

https://www.youtube.com/watch?v=P3YID7liBug