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 입니다. 검색 성공!