[알고리즘] 자바에서의 이진 탐색

이진 탐색(Binary Search)

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

 

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

- 분할 정복

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

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

 

- 이진 탐색

    - 리스트를 2개의 서브 리스트로 나눈다.

    - 검색할 숫자 > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.

    - 검색할 숫자 < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

    - 이진 탐색은 데이터가 정렬되어 있는 상태에서 진행한다.

 

자바 코드로 직접 작성해보자.,

- BinarySearch.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearch {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		list.add(3);
		list.add(6);
		list.add(17);
		list.add(1);
		list.add(9);
		list.add(5);
		list.add(4);
		
		Collections.sort(list);
		
		System.out.println(binarySearch(list, 17));
	}
	
	private static boolean binarySearch(List<Integer> list, int search) {
		
		if(list.size() == 1 && search == list.get(0))
			return true;
		
		if(list.size() == 1 && search != list.get(0))
			return false;
		
		if(list.size() == 0)
			return false;
		
		int middle = list.size() / 2;
		if(search == list.get(middle))
			return true;
		else {
			if(search > list.get(middle))
				return binarySearch(list.subList(middle, list.size()), search);
			else {
				return binarySearch(list.subList(0, middle), search);
			}
		}
	}
}

- 리스트의 길이가 1 이고, 리스트에 들어 있는 한개의 원소가 찾고 있는 값과 일치할 경우 true 를 반환한다.

- 리스트의 길이가 1 이고, 리스트에 들어 있는 한개의 원소가 찾고 있는 값과 일치하지 않을 경우 false 를 반환한다.

- 리스트의 길이가 0 이면(더 이상 리스트를 부분 리스트로 나눌 수 없으면) 해당 리스트에는 찾고자 하는 값이 없다는 뜻이므로 false 를 리턴한다.

- 리스트의 중간 길이를 구한 후 리스트에서 해당 인덱스에 있는 원소와 찾고자 하는 값을 비교하여, 만약 찾고자 하는 값과 일치하면 return true, 그렇지 않으면 다음 조건식을 진행한다.

- 찾고자 하는 값이 리스트의 중간 인덱스에 있는 값 보다 크면, 중간 인덱스 뒤로 이어지는 원소들을 묶어서 부분 리스트로 만들어준 후 binarySearch() 메소드를 재귀 호출한다.

- 반대로 찾고자 하는 값이 리스트의 중간 인덱스에 있는 값 보다 작으면, 중간 인덱스 앞에 이어지는 원소들을 묶어서 부분 리스트로 만들어준 후 binarySearch() 메소드를 재귀 호출한다.

 

 

알고리즘 분석

- n 개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산을 k 회 진행한다.

- 빅오 표기법으로는 k + 1 이 결국 최종 시간 복잡도이다.(1 이 되었을 때도 비교 연산을 한번 수행한다.)

- 결국 O(log2n + 1) 이고, 2와 1과 같은 상수는 삭제되므로 시간 복잡도는 O(log n) 이다.