이진 탐색(binary search)

데이터의 값이 오름차순과 내림차순으로 정렬 되어있는 배열에서 효과적으로 원하는 데이터의 값을 찾을 수 있는 알고리즘

🎈배열 a에서 원하는 값(39)를 검색하는 과정

n개의 요소를 가진 배열

🥦 맨 앞의 인덱스 : pl (0)
🥦 맨 끝의 인덱스 : pr (n-1)
🥦 중앙의 인덱스 : pc (n-1)/2
👉 검색할 대상이 두개 인 경우 pc의 값은 앞 인덱스로 간주한다.(나머지 버림)

🐼과정

1) a[pc] < key 일때
먼저 정렬된 배열에서 a[pc]의 값이 key 값보다 작으면 a[pc]값 이전의 값에는 있을 수 없으므로 탐색 대상에서 제외한다.
📍 다음 탐색 범위는 a[pc + 1] ~ a[pr]
📍 다음 pl 값 => pc + 1

2) a[pc] > key 일때
먼저 정렬된 배열에서 a[pc]의 값이 key 값보다 크면 a[pc]값 이전의 값에는 있을 수 없으므로 탐색 대상에서 제외한다.
📍 다음 탐색 범위는 a[pl] ~ a[pl-1]
📍 다음 pr 값 => pc - 1

🎈이진 탐색의 종료 조건

1) a[pc]와 key가 일치 하는 경우
2) 검색 범위가 더 이상 없는 경우

🎈알고리즘

class BinSearch {
	// 요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색합니다.
	static int binSearch(int[] a, int n, int key) {
		int pl = 0;			// 검색 범위의 첫 인덱스
		int pr = n - 1;		// 검색 범위의 끝 인덱스

		do {
			int pc = (pl + pr) / 2;		// 중앙 요소의 인덱스
			if (a[pc] == key)
				return pc;				// 검색 성공!
			else if (a[pc] < key)
				pl = pc + 1;			// 검색 범위를 뒤쪽 절반으로 좁힘
			else
				pr = pc - 1;			// 검색 범위를 앞쪽 절반으로 좁힘
		} while (pl <= pr);

		return -1;						// 검색 실패!
	}

public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.print("요솟수：");
		int num = stdIn.nextInt();
		int[] x = new int[num];				// 요솟수가 num인 배열

		System.out.println("오름차순으로 입력하세요.");

		System.out.print("x[0]：");			// 첫 요소 입력
		x[0] = stdIn.nextInt();

		for (int i = 1; i < num; i++) {
			do {
				System.out.print("x[" + i + "]：");
				x[i] = stdIn.nextInt();
			} while (x[i] < x[i - 1]);		// 바로 앞의 요소보다 작으면 다시 입력
		}

		System.out.print("검색할 값：");		// 키값을 입력
		int ky = stdIn.nextInt();

		int idx = binSearch(x, num, ky);	// 배열x에서 값이 ky인 요소를 검색

		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
	}
}![](https://velog.velcdn.com/images/tejava7177/post/fd6b17f1-e265-4c40-8453-3be0ca59e788/image.jpg)