이진탐색

이진 탐색...
구현할 줄 모르면 라이브러리만 붙잡고 어버버 한다.

이진 탐색 이란

검색 범위를 반으로 줄여가면서 검색하는 알고리즘.
단, 검색하는 자료가 순서에 따라 정렬 되어 있어야 한다.

1. 
중간인덱스 = (startindex + endindex) / 2
중간 인덱스의 값을 불러옴
2. 
구하려는 값을 중간 인덱스의 값과 비교
3. 
크면 start index = 중간인덱스 + 1
작으면 end index = 중간인덱스 -1
4. 
값을 찾을 때 까지 반복하기

구현

• 재귀를 통해 구현할 수 도 있다.

private static int binarySearch(List list, int score) {
		// 이진 탐색 시작
		int start = 0;
		int end = list.size() - 1;
		while( start <= end ) {
			int mid = (start + end) /2;
			// 찾는게 크면 시작을 미드보다 크게
            if (score == list.get(mid) ) return mid;
			if ( score > list.get(mid) ) {
				start = mid +1;
			}  else {
				// 찾는게 작으면 끝을 미드보다 작게
				end = mid -1;
			}
		}
		
		return 값이 없으면 여기
	}