이분탐색

 

 

 

배열이나 리스트에서 특정 원소를 찾을 때 탐색 알고리즘을 사용한다.

순차탐색은 말 그대로 맨 처음부터 탐색을 시작해 원하는 원소를 찾을 때 까지 탐색을 수행한다. ( O(n) )

 

좀 더 효율적으로 탐색하기 위해 이분 탐색 알고리즘이 고안됐다.

 

일단, 탐색하려는 배열이나 리스트는 정렬된 상태여야 한다.

 

1. 전체 데이터의 중간을 비교한다.

 

2. 찾으려는 원소와 중간 원소를 비교해 중간 원소보다 찾으려는 원소의 값이 더 작다면 중간값을 기준으로 좌측을, 그렇지 않으면 우측으로 탐색 구간을 재정의한다.

 

3. 1 2 를 반복한다.

 

만약 찾으려는 원소가 배열 안에 없어도 쉽게 파악할 수 있다.

 

미루어 짐작할 수 있듯, 이분 탐색도 분할정복 기법과 재귀를 사용하는 알고리즘이다.

 

 

import java.util.*;

public class BinarySearch {

    public boolean searchFunc(ArrayList<Integer> dataList, Integer searchItem) {
    // 탐색을 수행할 리스트와 찾고 싶은 인자로 설정한다.
    
        if (dataList.size() == 1 && searchItem == dataList.get(0)) {
            return true; // 탐색 성공
        } 
        
        if (dataList.size() == 1 && searchItem != dataList.get(0)) {
            return false; // 탐색 실패
        }
        
        if (dataList.size() == 0) {
            return false; // 탐색 실패
        }
        
        int medium = dataList.size() / 2; 
        
        if (searchItem == dataList.get(medium)) {
            return true;
        } else {
            if (searchItem < dataList.get(medium)) {
                return this.searchFunc(new ArrayList<Integer>(dataList.subList(0, medium)), searchItem); 
                // 재귀호출 
            } else {
                 return this.searchFunc(new ArrayList<Integer>(dataList.subList(medium, dataList.size())), searchItem);
                 // 재귀호출
            }
        }
    }
}

 

 

 

시간복잡도 : O(logn)