1. 검색 알고리즘
1-1. 선형검색(Sequential Search) 또는 순차검색(Linear Search)
- 무작위로 모인 데이터를 검색하는 수행 알고리즘
- 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘
1. for문을 사용해 linearSearch 메서드를 생성하고, 메서드 호출
1) main 메서드에서 데이터의 갯수를 입력받아서 배열을 생성하고
2) for문을 실행해서 배열에 입력받은 데이터를 삽입하고
3) 찾을 데이터를 입력받는다.
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("데이터수 ->");
int num = scan.nextInt();
// 배열을 생성
int[] data = new int[num]; // 5 -> 0,1,2,3,4
// 배열에 데이터삽입
for(int i=0; i<num; i++) {
System.out.print("data["+i+"]=");
data[i] = scan.nextInt();
}
// 찾을 숫자를 입력받는다.
System.out.print("검색할 데이터->");
int key = scan.nextInt();
}
4) 선형검색 메서드를 생성한다.(for문을 사용해 key의 값이 있는 위치를 구하여 index를 반환하는 메서드)
public class SequentialSearch {
// for문을 이용하여 검색하기
// 데이터담긴 배열, 데이터의 수, 찾을 데이터
static int linearSearch1(int[] data, int num, int key) {
// 배열에서 key값을 검색하여 index를 리턴한다.
// 만약 검색된 index가 없으면 -1을 리턴한다.
for(int i=0; i<num; i++) { // 0,1,2,3....
if(data[i]==key) {
return i; // 검색 성공!(인덱스를 반환)
}
}
return -1; // 검색 실패! -1을 반환
}
5) 선형검색 메서드 호출
// for를 사용한 선형검색 메서드호출
int idx = linearSearch1(data, num, key); // call by reference / -1,0,1,2,3..
if(idx>=0) { // 검색한 데이터가 있을 때(-1이 아니여서)
System.out.println(key + "는 data["+ idx +"]에 있습니다.");
} else { // 검색한 데이터가 없을 때
System.out.println(key + "는 존재하지 않는 데이터입니다.");
}
6) for문을 사용한 선형검색 메서드 코드
import java.util.Scanner;
public class SequentialSearch {
static int linearSearch1(int[] data, int num, int key) {
for(int i=0;i<num;i++) {
if(data[i]==key) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("데이터수->");
int num = scan.nextInt();
int[] data = new int[num]; // 5 -> 0,1,2,3,4
for(int i=0; i<num; i++) {
System.out.print("data["+i+"]=");
data[i] = scan.nextInt();
}
System.out.print("검색할 데이터->");
int key = scan.nextInt();
int idx = linearSearch1(data, num, key);
if(idx>=0) {
System.out.println(key + "는 data["+ idx +"]에 있습니다.");
} else {
System.out.println(key + "는 존재하지 않는 데이터입니다.");
}
scan.close();
}
}2. while 문을 사용해 linearSearch 메서드를 생성하고, 메서드 호출
1) main 메서드에서 데이터의 갯수를 입력받아서 배열을 생성하고
2) for문을 실행해서 배열에 입력받은 데이터를 삽입하고
3) 찾을 데이터를 입력받는다.
-> 1번과 동일하다.
4) 선형검색 메서드를 생성한다.(while문을 사용해 key의 값이 있는 위치를 구하여 index를 반환하는 메서드)
public class SequentialSearch {
// while문을 이용한 데이터의 인덱스 위치 검색
static int linearSearch2(int[] d, int num, int k) {
int i=0;
while(true) { // 0,1,2,3....
if(i==num) { // i index위치가 존재하는가
return -1; // 검색 실패! (-1 반환)
}
if(d[i]==k) { // 검색할 데이터를 찾은 경우
return i; // 검색 성공! (인덱스를 반환)
}
// 다음 index의 값을 확인하기 위해 index를 1증가
++i; // ++i, i++, i=i+1, i+=1 넷 중 하나
}
}
}
5) while문을 사용한 선형검색 메서드 호출
// while문을 이용한 선형검색 메서드 호출
int idx2 = linearSearch2(data, num, key);
if(idx2>=0) { // 검색한 데이터가 있을 때
System.out.println(key + "는 data["+ idx +"]에 있습니다.");
} else { // 검색한 데이터가 없을 때
System.out.println(key + "는 존재하지 않는 데이터입니다.");
}
6) while문을 사용한 선형검색 메서드 코드
import java.util.Scanner;
public class SequentialSearch {
static int linearSearch2(int[] d, int num, int k) {
int i=0;
while(true) {
if(i==num) {
return -1;
}
if(d[i]==k) {
return i;
}
++i;
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("데이터수->");
int num = scan.nextInt();
int[] data = new int[num]; // 5 -> 0,1,2,3,4
for(int i=0; i<num; i++) {
System.out.print("data["+i+"]=");
data[i] = scan.nextInt();
}
System.out.print("검색할 데이터->");
int key = scan.nextInt();
int idx2 = linearSearch2(data, num, key);
if(idx2>=0) {
System.out.println(key + "는 data["+ idx +"]에 있습니다.");
} else {
System.out.println(key + "는 존재하지 않는 데이터입니다.");
}
scan.close();
}
}
-> 값이 key인 요소가 여러 개 존재할 경우 반환 값은 검색 과정에서 처음 발견한 요소의 인덱스가 된다.
1-2. 이진검색(Binary Search)
- 요소가 일정한 규칙으로 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
- 중앙 값을 구해 중앙값이 찾을 값보다 작으면 오른쪽으로 검색하고, 찾을 값보다 크면 왼쪽으로 검색한다.
- 이진검색은 선형검색보다 좀 더 빠르게 검색할 수 있다!
1. do-while 문을 사용해 binarySearch 메서드를 생성하고, 메서드 호출
1) main 메서드에서 데이터의 수를 입력받아서 배열을 생성하고
2) for문을 실행해서 배열에 입력받은 데이터를 삽입하고
3) 찾을 데이터를 입력받는다.
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("데이터수 = ");
int n = scan.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) {
System.out.print("arr["+i+"]= ");
arr[i] = scan.nextInt();
}
// 검색할 수 입력
System.out.println("검색할 데이터 = ");
int key = scan.nextInt();
}
4) 이진 검색 메서드를 생성한다.(do while문을 사용해 key의 값이 있는 위치를 구하여 index를 반환하는 메서드)
public class BinarySearch {
static int binarySearch(int[] arr, int n, int key) {
int left = 0; // 왼쪽 시작 index
int right = n-1; // 오른쪽 마지막 index(배열의 크기 n, 마지막 배열의 크기n-1)
do { // do-while문으로 최소 한 번은 실행
// 중간 index를 구한다.
int center = (left + right)/2;
if(key == arr[center]){ // 검색할 값이 중간 index에 있을 경우
return center; // center index 반환
} else if(arr[center] < key) { // 찾으려는 값이 중앙값보다 크면
left = center+1; // left를 center+1로 바꾼다.(오른쪽으로)
} else { // 찾으려는 값이 중앙값보다 작으면
right = center-1; // right를 center-1로 바꾼다.(왼쪽으로)
}
} while(left<=right); // 검색한 값이 없을 경우
return -1;
}
5) 이진검색 메서드 호출
// 이진검색 메서드 호출
int result = binarySearch(arr,n,key);
if(result>=0) { // 검색한 데이터가 있을 때
System.out.println(key + "는 arr["+ result +"]에 있습니다.");
} else { // 검색한 데이터가 없을 때
System.out.println(key + "는 존재하지 않는 데이터입니다.");
}
<전체 코드>
import java.util.Scanner;
public class BinarySearch {
static int binarySearch(int[] arr, int n, int key) {
int left = 0;
int right = n-1;
do {
int center = (left + right)/2;
if(key == arr[center]){
return center;
} else if(arr[center] < key) {
left = center+1;
} else {
right = center-1;
}
} while(left<=right);
return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("데이터수 = ");
int n = scan.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) {
System.out.print("arr["+i+"]= ");
arr[i] = scan.nextInt();
}
System.out.println("검색할 데이터 = ");
int key = scan.nextInt();
int result = binarySearch(arr,n,key);
if(result>=0) { // 검색한 데이터가 있을 때
System.out.println(key + "는 arr["+ result +"]에 있습니다.");
} else { // 검색한 데이터가 없을 때
System.out.println(key + "는 존재하지 않는 데이터입니다.");
}
scan.close();
}
}
'멀티캠퍼스 풀스택 과정 > 알고리즘' 카테고리의 다른 글
| 알고리즘2-1. 선형리스트(LinkedList 연결리스트) (0) | 2022.01.27 |
|---|---|
| 알고리즘1-6. 정렬(Sorting): 버블정렬, 선택정렬, 삽입정렬, 퀵정렬 (0) | 2022.01.26 |
| 알고리즘1-5. 재귀알고리즘 (0) | 2022.01.26 |
| 알고리즘1-4. 큐(Queue) (0) | 2022.01.26 |
| 알고리즘1-1. 알고리즘이란? (0) | 2022.01.25 |
