이진 검색

Binary Search
요소가 오름차순 혹은 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

p1 검색 범위의 맨 앞 인덱스
pc 중앙 인덱스
pr 마지막 인덱스

1. a[pc] < key일 때,
검색 범위를 a[pc+1] ~ a[pr]로 좁힌다. p1의 값을 pc+1로 업데이트 해준다.

2. a[pc] > key일 때,
검색 범위를 a[p1] ~ a[pc-1]로 좁힌다. pr의 값을 pc-1로 업데이트 해준다.

이진 검색 기본 연습

import java.util.Scanner;

public class BinarySearch {

	static int binary(int[] a, int n, int key) {
		// element의 수가 n개인 배열 a에서 key와 같은 값을 찾는다.
		int p1 = 0; // 검색 범위의 맨 처음 index
		int pr = n - 1; // 검색 범위의 마지막 index

		do {
			int pc = (p1 + pr) / 2; // 검색 범위의 중앙 index
			if (a[pc] == key)
				return pc;
			else if (a[pc] < key)
				p1 = pc + 1;
			else // a[pc]>key인 경우
				pr = pc - 1;
		} while (p1 <= pr);

		return -1; // 검색 실패
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("num of element : ");
		int n = sc.nextInt();
		int[] a = new int[n];

		System.out.print("오름차순으로 입력 : ");

		System.out.print("a[0] : ");
		a[0] = sc.nextInt();

		for (int i = 1; i < n; i++) {
			do {
				System.out.print("a[ " + i + " ] : ");
				a[i] = sc.nextInt();
			} while (a[i] < a[i - 1]); // 이전에 입력한 요소보다 작으면 다시 입력
		}

		System.out.print("검색할 값 : ");
		int key = sc.nextInt();

		int result = binary(a, n, key);

		if (result == -1)
			System.out.println("검색 실패");
		else
			System.out.println("a[" + result + "] :" + a[result] + " 입니다. 검색 성공!");

	}

}

num of element : 6
오름차순으로 입력 : a[0] : 1
a[ 1 ] : 3
a[ 2 ] : 5
a[ 3 ] : 8
a[ 4 ] : 25
a[ 5 ] : 35
검색할 값 : 3
a[1] :3 입니다. 검색 성공!