반응형
선형검색
앞부터 순서대로 검색 하는 방법
package javaStudy;
import java.util.Scanner;
public class ch3_2 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("배열 수 : ");
int num = stdIn.nextInt();
int[] x = new int[num];
for (int i = 0; i < x.length; i++) {
System.out.print("x[i] : ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값 : ");
int key = stdIn.nextInt();
int res = seqSearch(x, num, key);
if(res!=-1) {
System.out.println(key+ "값은 " + (res+1) + "번째에 있습니다.");
}else {
System.out.println("찾는 값이 없습니다.");
}
}
//선형검색
public static int seqSearch(int[] a, int n, int key) {
for (int i = 0; i < a.length; i++) {
if(a[i]==key) {
return i;
}
}
return -1;
}
}
이진검색
이진검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다.
- 오름차순으로 입력된 배열 a[9]에서 데이터 39를 이진검색을 이용하여 검색해봅시다.
| a[0] = 5 | a[1] = 7 | a[2] = 15 | a[3] = 28 | a[4] = 29 | a[5] = 31 | a[6] = 39 | a[7] = 58 | a[8] = 68 | a[9] = 70 |
1. 배열의 중앙에 위치한 a[4] = 29를 찾습니다. 검색하려는 값(39)이 29보다 크기 때문에 a[4]보다 큰 배열로 검색 대상을 좁힙니다.
| a[0] = 5 | a[1] = 7 | a[2] = 15 | a[3] = 28 | a[4] = 29 | a[5] = 31 | a[6] = 39 | a[7] = 58 | a[8] = 68 | a[9] = 70 |
2. 새로운 검색 범위의 중앙값 a[7]을 찾습니다. 검색하려는 값(39)이 58보다 작기 때문에 a[7]보다 작은 배열로 검색 대상을 좁힙니다.
| a[0] = 5 | a[1] = 7 | a[2] = 15 | a[3] = 28 | a[4] = 29 | a[5] = 31 | a[6] = 39 | a[7] = 58 | a[8] = 68 | a[9] = 70 |
3. 새로운 검색 범위의 중앙값을 찾습니다. 둘 중 (5+6) /2 은 5이기 때문에 a[5]부터 검색하여 원하는 값인지 확인 하고 검색대상을 좁혀 검색값을 찾습니다.
| a[0] = 5 | a[1] = 7 | a[2] = 15 | a[3] = 28 | a[4] = 29 | a[5] = 31 | a[6] = 39 | a[7] = 58 | a[8] = 68 | a[9] = 70 |
package javaStudy;
import java.util.Scanner;
public class ch3_3 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("배열 수 : ");
int num = stdIn.nextInt();
int[] x = new int[num];
System.out.print("x[0] :");
x[0] = stdIn.nextInt();
// 이진검색의 전제조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다고 가정.
// 오름차순으로 입력을 차례대로 받는 부분
for (int i = 1; i < x.length; i++) {
do {
System.out.print("x["+i+"] :");
x[i] = stdIn.nextInt();
} while (x[i] < x[i-1]);
}
System.out.print("검색할 값 : ");
int key = stdIn.nextInt();
int res = binarySearch(x, num, key);
if(res!=-1) {
System.out.println("검색 값은 " + (res+1) + "번 째에 있습니다.");
}else {
System.out.println("검색 한 값이 없습니다.");
}
}
// 이진검색
public static int binarySearch(int[] a, int num, int key) {
int max = num-1; //0부터 시작이기 때문에
int min = 0;
int i = 0;
do {
i = (min+max)/2;
if(a[i] < key) {
min = i+1;
}else if(a[i] > key) {
max = i-1;
}else if(a[i] == key) {
return i;
}
} while (min <= max);
return -1;
}
}
java에서 이진검색 표준 라이브러리 메서드를 제공합니다.
- java.util.Arrays 클래스의 binarySearch 메서드
검색에 실패한 경우 검색값 보다 큰 요소 중 첫번째 값의 인덱스를 x라 하고 -x-1 값을 반환 합니다.
- 이진검색 라이브러리를 사용하면 이진검색 메서드를 직접 코딩 할 필요 없이 간단하게 표현 가능합니다. 모든 자료형 배열에서 검색 가능합니다.
package javaStudy;
import java.util.Arrays;
import java.util.Scanner;
public class ch3_3 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("배열 수 : ");
int num = stdIn.nextInt();
int[] x = new int[num];
System.out.print("x[0] :");
x[0] = stdIn.nextInt();
// 이진검색의 전제조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다고 가정.
// 오름차순으로 입력을 차례대로 받는 부분
for (int i = 1; i < x.length; i++) {
do {
System.out.print("x["+i+"] :");
x[i] = stdIn.nextInt();
} while (x[i] < x[i-1]);
}
System.out.print("검색할 값 : ");
int key = stdIn.nextInt();
//int res = binarySearch(x, num, key);
int res = Arrays.binarySearch(x, key);
if(res!=-1) {
System.out.println("검색 값은 " + (res+1) + "번 째에 있습니다.");
}else {
System.out.println("검색 한 값이 없습니다.");
}
}
}
- Do it 자료구조와 함께 배우는 알고리즘 입문 자바편 스터디 정리
반응형
'개발 > algorithm' 카테고리의 다른 글
| [C/C++][algorithm] 삽입정렬 (0) | 2019.10.30 |
|---|---|
| [C/C++][algorithm] 선택정렬 (0) | 2019.10.28 |
| [java][algorithm]소수 구하기 (0) | 2018.10.07 |
| [java][algorithm] 기수 변환 (10진수 정수 n진수 정수로 변환) (0) | 2018.10.07 |
| [java][algorithm] 배열 역순으로 정렬하기, 배열 뒤집기 (0) | 2018.10.07 |