[배열 검색] 이진 검색
이진 검색은 선형 검색보다 빠르게 검색할 수 있는 검색 알고리즘이다.
이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서만 사용할 수 있는 알고리즘이다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수를 입력하세요: ");
int N = sc.nextInt();
int[] arr = new int[N];
System.out.println("오름차순으로 입력하세요.");
System.out.print("arr[0]: ");
arr[0] = sc.nextInt();
for (int i = 1; i < arr.length; i++) {
do {
System.out.print("arr[" + i + "]: ");
arr[i] = sc.nextInt();
} while (arr[i] < arr[i - 1]); // 바로 앞의 요소보다 작으면 다시 입력.
}
System.out.print("검색할 값: ");
int key = sc.nextInt();
int idx = binSearch(arr, key, N);
if (idx == -1) {
System.out.println("그 값의 요소는 없습니다.");
} else {
System.out.printf("%d은(는) arr[%d]에 있습니다.", key, idx);
}
}
static int binSearch(int[] arr, int key, int n) {
int pl = 0;
int pr = n - 1;
do {
int pc=(pl+pr)/2; //배열의 중앙값
if(arr[pc]<key) { //key 값이 더 크면
pl=pc+1;
}else if(key<arr[pc]) {//key 값이 더 작으면
pr=pc-1;
}else {
return pc;
}
} while (pl <= pr);
return -1;
}
}오름차순 이진검색
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수를 입력하세요: ");
int N = sc.nextInt();
int[] arr = new int[N];
System.out.println("내림차순으로 입력하세요.");
System.out.print("arr[0]: ");
arr[0] = sc.nextInt();
for (int i = 1; i < arr.length; i++) {
do {
System.out.print("arr["+i+"]: ");
arr[i]=sc.nextInt();
}while(arr[i]>arr[i-1]);
}
System.out.print("검색할 값: ");
int key = sc.nextInt();
int idx = binSearch(arr, key, N);
if (idx == -1) {
System.out.println("그 값의 요소는 없습니다.");
} else {
System.out.printf("%d은(는) arr[%d]에 있습니다.", key, idx);
}
}
static int binSearch(int[] arr, int key, int n) {
int pl = 0;
int pr = n - 1;
do {
int pc=(pl+pr)/2;
if(arr[pc]==key) {
return pc;
}else if(arr[pc]<key) {
pr=pc-1; //pr을 index 감소시킴
}else {
pl=pc+1; //pl을 index 증가시킴
}
} while (pl <= pr);
return -1;
}
}내림차순 이진 검색
요솟수를 입력하세요: 5
내림차순으로 입력하세요.
arr[0]: 50
arr[1]: 45
arr[2]: 22
arr[3]: 10
arr[4]: 1
검색할 값: 22
22은(는) arr[2]에 있습니다.
복잡도
알고리즘 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.
복잡도는 2가지 요소를 가지고 있다.
1. 시간 복잡도(time complexity): 실행에 필요한 시간을 평가하는 것.
2. 공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가하는 것.
이진 검색의 시간 복잡도는
static int binSearch(int[] arr, int key, int n) {
int pl = 0; //1
int pr = n - 1; //2
do {
int pc=(pl+pr)/2; //3
if(arr[pc]==key) { //4
return pc; //5
}else if(arr[pc]<key) { //6
pr=pc-1; //7
}else {
pl=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는 Order를 뜻한다. O(n)은 'O-n', 'Order n', 'n의 Order'라고 읽는다.)
복잡도는 차원이 가장 높은 복잡도를 선택한다.
그래서,
O(1)+O(1)+O(log n)+O(log n)+....+O(1)= O(log n)
따라서, 위 이진 검색 메서드의 시간 복잡도는 O(log n)이다.
Arrays.binarySearch 메서드
java.util 패키지에 있는 Arrays 클래스 내에 binarySearch 메서드는 위에 코드들처럼 손 수 이진 검색 알고리즘을 작성하지 않고 사용할 수 있는 메서드이다.
binarySearch는 요소수를 찾을 시 해당 index를 반환한다.
만약 못 찾을 경우에는
반환 값은 삽입 포인트 x라고 할 때 -x-1을 반환한다.
삽입 포인트는 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스가 삽입 포인트이다.
만약, arr {5.10.15,20} 배열에서 11을 검색하면
11보다 큰 요소는 15이다. 15의 값을 가진 요소의 index는 2이므로
-2-1 = -3
-3을 반환하게 된다.
위 그림처럼 key값이 요소들보다 전부 다 클 경우 마지막 인덱스 바로 뒤에 임시로 길이를 1 추가해 -추가된 index-1을 반환한다.
import java.util.*; //Arrays.binarySearch 사용하기 위한 import
public class Search {
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
System.out.print("요소수를 입력하세요: ");
int N = sc.nextInt();
int[] arr = new int[N];
System.out.print("arr[0]: ");
arr[0] = sc.nextInt();
for (int i = 1; i < arr.length; i++) {
do {
System.out.print("arr[" + i + "]: ");
arr[i] = sc.nextInt();
} while (arr[i] < arr[i - 1]);
}
System.out.print("찾으려는 요소값은?: ");
int key = sc.nextInt();
int value = Arrays.binarySearch(arr, key);
if (value < 0) {
System.out.println("찾으려는 요소값은 없습니다." + value);
} else {
System.out.println("찾으려는 " + key + "는 arr[" + value + "]에 있습니다.");
}
}
}
요소수를 입력하세요: 5
arr[0]: 1
arr[1]: 2
arr[2]: 3
arr[3]: 4
arr[4]: 5
찾으려는 요소값은?: 4
찾으려는 4는 arr[3]에 있습니다.binarySearch메서드로 검색을 성공한 경우
요소수를 입력하세요: 4
arr[0]: 15
arr[1]: 52
arr[2]: 88
arr[3]: 100
찾으려는 요소값은?: 87
찾으려는 요소값은 없습니다.-3찾으려는 요소 값이 존재하지 않는다면.
Arrays.binarySearch에 의한 이진 검색의 장점은
1. 이진 검색 메서드를 직접 코딩하지 않아도 된다.
2. 모든 자료형 배열에서 검색할 수 있다.
import java.util.*;
public class langTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] strArr = { "Java", "C", "C++", "Python" };
String key = sc.next();
int idx = Arrays.binarySearch(strArr, key);
if (idx < 0) {
System.out.println("해당 문자열은 존재하지 않습니다.");
} else {
System.out.println("해당 문자열은 strArr[" + idx + "] 에 있습니다.");
}
}
}C++
해당 문자열은 strArr[2] 에 있습니다.검색 성공
python
해당 문자열은 존재하지 않습니다.p가 소문자라 검색 실패
위에 코드처럼 binarySearch메서드는 모든 자료형 배열에서 검색할 수 있다는 장점이 있다.
참고하면 좋은 자료
이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전
이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고
ko.wikipedia.org
커버 사진
<a href="https://www.flaticon.com/kr/free-icons/" title="연산 아이콘"> 연산 아이콘 제작자: khld939 - Flaticon </a>