Doit자바 알고리즘 - 검색 알고리즘(이진검색)
업데이트:
이진 검색(binary search)
이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.
검색의 범위를 절반으로 줄여서 검색시간을 대폭 줄일 수 있다. 다만, 이진 검색은 배열이 반드시 순차정렬되어있는 것을 전제로 한다.
- 이진 검색 알고리즘 예제
package com.practiceExample.Doit.chap03;
import java.util.Scanner;
// 이진 검색
public class BinSearch {
// 요솟수가 num인 배열 arr에서 key와 같은 요소를 이진 검색한다.
static int binSearch(int[] arr, int num, int key) {
int pl = 0; //검색 범위의 첫 인덱스
int pr = num-1;
do {
int pc = (pl + pr) / 2; // 중앙 요소의 인덱스
if(arr[pc] == key) {
return pc; // 검색에 성공했음!
} else if (arr[pc] < key) {
pl = pc + 1; // 검색 범위를 뒤쪽 절반으로 좁힌다.
} else {
pr = pc - 1; // 검색 범위를 앞쪽 절반으로 좁힘.
}
} while(pl <= pr);
return -1; // 검색 실패!
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("요솟수 : ");
int num = scanner.nextInt();
int[] x = new int[num]; //요솟수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0] : "); // 첫 요소를 입력
x[0] = scanner.nextInt();
for(int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "] : ");
x[i] = scanner.nextInt();
} while(x[i] < x[i-1]); // 바로 앞의 요소보다 작으면 다시 입력
}
System.out.print("검색할 값 : "); // key값을 입력한다.
int key = scanner.nextInt();
int idx = binSearch(x, num, key); //배열 x에서 키값이 key인 요소를 검색한다.
if(idx == -1) {
System.out.println("그 값의 요소가 없습니다.");
} else {
System.out.println(key + "은(는) x[" + idx + "]에 있습니다.`" );
}
scanner.close();
}
}
복잡도
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다.
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다. 복잡도는 아래의 두 가지 요소를 가지고 있다.
- 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것
- 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
선형 검색의 시간 복잡도
static int seqSearch(int[] a, int n, int key) {
1 int i = 0;
2 while (i < n) {
3 if(a[i] == key) {
4 return i; // 검색 성공
}
5 i++;
}
6 return -1; // 검색 실패
}
변수 i에 0을 대입(1번라인)하는 횟수는 처음 한 번 실행한 이후로 없다.(데이터 수 b과는 무관하다.) 이렇게 한 번만 실행하는 경우 복잡도는 O(1)로 표기한다. 물론 메서드에서 값을 반환하는 4, 6라인도 한 번만 실행하기 때문에 O(1)로 표기한다. 배열에 맨 끝에 도달했는지 판단하는 2번라인과 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지를 판단하는 3번 라인의 평균 실행 횟수는 n / 2이다. 이처럼 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)으로 표기한다.
복잡도를 표기할때의 O는 Oreder에서 따온 것으로, O(n)은 ‘O - n’, ‘Order n’, ‘n의 Order’라고 읽는다.
2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시한다. 둘이 아니라 셋 이상의 계산으러 구성된 알고리즘도 마찬가지이다. 다시 말해 전체 복잡도는 차원이 가장 높은 복잡도를 선택한다. 그러므로 선형 검색 알고리즘의 복잡도를 구하면 아래처럼O(n)이 된다.
O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)
댓글남기기