[알고리즘] 이진 탐색

 

 

1.  이진 탐색 

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

- 이진 탐색을 사용하려면 필수적으로 데이터가 정렬이 되어있어야 한다.

 

 

 

2. 이진 탐색의 예시

 

- 예를 들어 내가 37이라는 데이터를 찾고자 한다면, 전체 데이터 중 중간의 값을 확인해서

   내가 찾고자 하는 데이터와 비교해준다.

  - 중간의 값이 23 이므로, 23 < 37 이기 때문에 23의 오른쪽으로 이동한다.

  - 그리고 그중 중간의 값을 확인하여 37과 비교해준다.

  - 중간의 41 이 37 보다 크기 때문에 37은 41의 왼쪽에 존재할 것이므로, 왼쪽으로 이동한다.

  - 그리고 그 중간 값 31이 37 보다 작기 때문에 37은 31의 오른쪽에 존재할 것이고, 37을 찾을 수 있다.

 

- 순차 탐색의 경우 찾으려고 하는 데이터가 위치하는 index 만큼의 시간이 걸리는데 

- 이진 탐색의 경우 순차 탐색보다 데이터를 훨씬 빠르게 찾을 수 있다.

 

 

 

 

3. 알고리즘 구현 

public class BinarySearch {

	public boolean searchFunc (ArrayList<Integer> data, Integer item) {
		if (data.size() == 1 && item == data.get(0)) {
			return true;
		}

		if (data.size() == 1 && item != data.get(0)) {
			return false;
		}

		if (data.size() == 0) {
			return false;	
		}

		int medi = data.size()/2;

		if (item == data.get(medi)) {
			return true;
		} else {
			if (item < data.get(medi)){
				return this.searchFunc(new ArrayList<Integer>(data.subList(0, medi)), item);	
			} else {
				return this.searchFunc(new ArrayList<Integer>(data.subList(medi, data.size())), item);
			}
		}
	}
}

 

- 이 알고리즘을 분석해보면 n 개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산을 k회 진행하고 있다.

- 빅 오 표기법으로는 k + 1 이 최종 시간 복잡도 이므로 O(log n) 로 표현된다.