찰떡개발자 코딩

알고리즘에 대해서 너무 모르는것 같아 하나씩 시간 날때마다 공부해 보려고 한다.

이진탐색 알고리즘이란

정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용

이진 탐색은 '퀵정렬'과 유사하게 '분할 후 정복(divide and conquer)'의 전략을 사용

실행시간은 log

특히 문제의 크기를 정확히 양분하는 경우에는 최악의 경우 logN의 성능을 보장한다.

 이진 탐색의 탐색 시간은 'T = K * logN'으로 O(logN)이다. 선형 탐색의 시간보다 상당히 빠르지만 이진 탐색은 반드시 정렬이 되어있어야 한다. 정렬하는 비용이 든다는 단점이 있다.

다음과 같은 상황에서 이진 탐색은 효율적인 성능을 제공한다.

 1) 새로운 자료가 추가되었어도 모든 자료가 재정렬이 일어나지 않는 경우 -> 해싱, 인덱스를 이용하는 경우

 2) 획기적으로 빠르고, 효율적인 자료의 재정렬이 가능한 자료 구조를 사용할 경우 -> B-트리 계열의 트리 구조 사용

이 알고리즘은 우선 중간을 설정하여 0~ 중간 중간+1에서 List.size() 까지 나눠서 탐색하는 알고리즘이다.

방법은 여러가지가 있고, 재귀를 통한 탐색을 해보려고 한다.

• 재귀를 통한 풀이

 public static void main(String[] args) {
		int[] numbers = {1,2,3,4,5,6,7,8,9,10,11,12,13};
		//ArrayList에 담아놓는다.
		List<Integer> list = new ArrayList<Integer>();
		for(int i=0; i<numbers.length; i++) //Array to List
			list.add(numbers[i]);

		binarySearch(list, 2);
	}

    //재귀 함수로 사용한다.
	public static void binarySearch(List<Integer> numbers, Integer value){

		if(numbers == null || numbers.isEmpty()){
			return;
		}

		//비교대상
		Integer mid = numbers.get(numbers.size()/2);
		System.out.println("기준값 : "+mid);

		if(value.equals(mid)){
			System.out.println("결과 : " + mid+ "|| 값 : "+value);
			return;
		}

		//재귀
		if(value < mid){
			//subList() : 리스트 일부 추출
			binarySearch(numbers.subList(0, numbers.size()/2), value); //앞에서 중간까지
		}else{
			binarySearch(numbers.subList(numbers.size()/2+1, numbers.size()), value); //중간+1 부터 끝까지
		}
	}

결과 : 

기준값 : 7
기준값 : 4
기준값 : 2
결과 : 2|| 값 : 2

알아야 할것이 너무너무너무 많지만 ...~ 멈춰있는것 보다는 훨씬 났다는거..!