1. 이진 검색
이진 검색(binary search)
- 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
- pl = 검색 범위의 맨 앞 인덱스 , 0
- pr = 검색 범위의 맨 끝 인덱스 , n-1
- pc = 검색 범위의 중앙 인덱스 , (n-1)/2
- 이진 검색을 한 단계씩 진행할 때마다 검색범위가 반으로 좁혀짐
1) a[pc] < key 일 때
- a[pl] ~ a[pc]는 key보다 작은 것이 분명하므로 검색대상에서 제외
- 검색 범위를 중앙 요소 a[pc]보다 뒤쪽인 a[pc+1] ~ a[pr]로 좁힘
- pl값을 pc+1로 업데이트
2) a[pc] >key일 때
- a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외
- 검색 범위를 중앙 요소 a[pc]보다 앞쪽인 a[pl] ~ a[pc-1]로 좁힘
- pr 값을 pc-1로 업데이트
3) 이진 검색 알고리즘의 종료 조건
1. a[pc]와 key가 일치
2. 검색 범위가 더 이상 없음 (pr<pl이 되면 검색 종료!)
//이진 검색
import java.util.Scanner;
public 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 sc = new Scanner(System.in);
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num]; //요솟수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.println("x[0]: "); //첫 요소를 입력 받음
x[0] = sc.nextInt();
for(int i=1; i<num; i++) {
do {
System.out.print("x["+i+"]: ");
x[i] = sc.nextInt();
}while(x[i]<x[i-1]); //바로 앞의 요소보다 작으면 다시 입력받음
}
System.out.print("검색할 값: ");
int key = sc.nextInt();
int index = binSearch(x,num,key); //배열 x에서 값이 key인 요소를 검색
if(index ==-1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x["+index+"]에 있습니다.");
}
}
2. 복잡도
복잡도(complexity)
- 알고리즘의 성능을 객관적으로 평가하는 기준
- 시간 복잡도(time complexity)
-> 실행에 필요한 시간을 평가한 것
- 공간 복잡도(space complexity)
-> 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
1) 선형 검색의 시간 복잡도
static int seqSearch(int[] a, int n, int key)
{
int i=0; //1)
while(i<n){ //2)
if(a[i] == key) //3)
return i; //4)
i++; //5)
}
return -1; //6)
}
- 각 단계별 실행 횟수
| 단계 | 실행 횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | n/2 | O(n) |
| 3 | n/2 | O(n) |
| 4 | 1 | O(1) |
| 5 | n/2 | O(n) |
| 6 | 1 | O(1) |
- 한 번만 실행하는 복잡도는 O(1)
- 배열의 맨 끝에 도달했는지를 판단하는지(2)와 현재 선택한 요소와 찾고자 하는 값이 같은지를 판단하는 (3)의 평균 실행 횟수는 n/2
-> n에 비례하는 횟수만큼 실행하는 복잡도는 O(n)
- 2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차수가 더 높은 쪽의 복잡도가 지배
O(1)+O(n)+O(n)+O(1)+O(n)+O(1) = O(max(1,n,n,1,n,1)) = O(n)
2) 이진 검색의 시간 복잡도
static int binSearch(int[] a, int n, int key)
{
int pl = 0; //검색 범위의 첫 인덱스 1)
int pr = n-1; //검색 범위의 끝 인덱스 2)
do {
int pc = (pl+pr)/2; //중앙 요소의 인덱스 3)
if(a[pc] ==key) //4)
return pc; //검색 성공 5)
else if(a[pc]<key) //6)
pl=pc+1; //검색 범위를 뒤쪽 절반으로 좁힘 7)
else
pr=pc-1; //검색 범위를 앞쪽 절반으로 좁힘 //8)
}while(pl<=pr); //9)
return -1; //검색 실패 //10)
}
- 각 단계별 실행 횟수
| 단계 | 실행 횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | 1 | O(1) |
| 3 | log n | O(log n) |
| 4 | log n | O(log n) |
| 5 | 1 | O(1) |
| 6 | log n | O(log n) |
| 7 | log n | O(log n) |
| 8 | log n | O(log n) |
| 9 | log n | O(log n) |
| 10 | 1 | O(1) |
이진 검색 복잡도
O(1)+O(1)+O(log n)+O(log n)+...+O(1) = O(log n)
3. Arrays.binarySearch에 의한 이진 검색
- 배열에서 이진 검색을 하는 메서드
- 오름차순으로 정렬된 배열 a를 가정하고 값이 key인 요소를 이진 검색
- 자료형과 관계없이 검색할 수 있도록 자료형에 따라 9가지 방법으로 오버로딩됨
1) 검색에 성공한 경우
- key와 일치하는 요소의 인덱스를 반환
2) 검색에 실패한 경우
- 배열 안에 key가 있어야 할 위치(삽입 포인트)를 추정할 수 있는 값을 반환
- 삽입 포인트를 x라고 할 때 반환 값은 -x-1
- 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스
ex) 31을 검색
- 31을 검색하면 31은 인덱스(4)와 인덱스(5) 사이에 위치해야 하므로 삽입 포인트는 5
- -6을 반환
ex) 95를 검색
- 95를 검색하면 모든 요소가 검색하는 값보다 작기 때문에 삽입 포인트는 배열의 길이인 10이 됨
- -11을반환
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearchTester {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num]; //요솟수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: ");
x[0] = sc.nextInt();
for(int i=1; i<num; i++) {
do {
System.out.print("x["+i+"]: ");
x[i] = sc.nextInt();
}while(x[i]<x[i-1]); //바로 앞의 요소보다 작으면 다시 입력받음
}
System.out.print("검색할 값: ");
int key = sc.nextInt();
int index = Arrays.binarySearch(x, key); //배열 x에서 값이 key인 요소를 검색
if(index < 0)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x["+index+"]에 있습니다.");
}
}
