[ 자바 알고리즘/자료구조] - 자바 이진탐색

이진탐색

- 오름차순 or 내림차순으로 정렬되어있는 배열에서 검색하는 알고리즘

 

-> 7찾기

step 1)

start			center			end
5	7	9	11	13	15	17

step 2)

start	center	end
5	7	9

 

- 이진탐색을 시작(0), 중앙( (배열길이 - 1 / 2) ) , 끝( 배열길이 - 1)으로 나눈다.

- 찾는 값이 중앙 값 보다 작다면 -> 시작(0), 끝( 중앙-1 ),  중앙 ( (배열길이 - 1 / 2) )가 되고

- 찾는 값이 중앙 값 보다 크다면 -> 시작(중앙+1) , 끝( 배열길이 -1 ), 중앙 (배열길이 -1/2)가 된다.

 

종료조건

- 1) 중앙값과 key가 일치

- 2) 검색 범위에서 찾지 못함

 

시간복잡도

- 반복마다 검색 범위가 반으로 줄어든다

- 평균 : log n

- 성공 : log n - 1

- 실패 : log(n+1)

 

public class 이진검색 {
	static int binSearch(int[] a, int n, int key) {
		int start = 0; //시작 인덱스
		int end = n - 1; //끝 인덱스
		
		do {
			int center = (start + end) / 2; //중앙 인덱스
			if(a[center] == key) {
				return center;
			}else if(a[center] < key) {
				start = center + 1;
			}else {
				end = center - 1;
			}
		}while(start <= end);
		
		return -1;
	}
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int key = s.nextInt();
		int arr[] = { 33, 12, 57, 24, 81, 77, 91, 45 };
		Arrays.sort(arr);
		System.out.println(Arrays.toString(arr));
		int idx = binSearch(arr, arr.length, key);
		if(idx >= 0)
			System.out.println("찾는 값의 인덱스 : " + idx);
		else
			System.out.println("요소가 없습니다.");
	}
}