탐색 알고리즘 | 이진 탐색(Binary Search)

1. 이진 탐색(Binary Search)이란?

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 

* 데이터가 정렬되어 있어야함

 

 2. 분할 정복 알고리즘과 이진 탐색 

분할 정복 알고리즘(Divide and Conquer)

Divide : 문제를 하나 또는 둘 이상으로 나눈다. 

Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 

이진 탐색 

Divide : 리스트를 두 개의 서브 리스트로 나눈다. 

Comquer : 검색할 숫자(search) > 중간값이면, 뒷부분 / < 면 서브 리스트에서 검색할 숫자를 찾는다. 

import java.util.ArrayList;

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.searhFunc(new ArrayList<Integer>()(dataList.subList(medium, dataList.size())), searchItem);
            }
    	}
    }
}


ArrayList<Integer> testData = new ArrayList<Integer>();

for(int index = 0; index < 100; index++) {
	testData.add(int)(Math.random() * 100));
}

Collections.sort(testData);
System.out.println(testData);


BinarySearch bSearch = new BinarySearch();
bSearch.searchFunc(testData, 2);

 

알고리즘 분석

시간복잡도 O(logn)