[JAVA] 이진탐색(Binary Search)

이진탐색(Binary Search)

효율적인 검색(탐색)기법인 이진탐색에 대해 알아보겠습니다.

탐색시 리스트가 정렬되어 있지 않으면 리스트 검색 시 주어진 값을 찾기위해 모두를 찾아봐야한다는 단점이 있습니다. 

하지만 정렬된 리스트가 있거나 검색전에 정렬을 수행한 경우 이진 탐색(binary Search)을 사용하면 매우 효과적으로 원하는 값을 얻을 수 있습니다.

=> 이진탐색은 원소를 일일이 비교하지 않고도 주어진 원소를 찾을 수 있으며, 백만 개의 원소가 있어도 20번 미만의 비교로 주어진 원소를 찾을 수 있습니다. O(logn) 

package algorithm;
 
import java.util.List;
 
public class BinarySearch {
    public boolean binarySearch(final List<Integer> input, final Integer value) {
        if(input.size() == 0)
            return false;
        
        final int comparision = input.get(input.size()/2);
        if(comparision == value)
            return true;
        
        if(value > comparision) {
            return binarySearch(input.subList(input.size()/2, input.size()), value);
        }else {
            return binarySearch(input.subList(0, input.size()/2), value);
        }
        
    }
}