선형 검색
알고리즘 1
class MainClass {
static int seqSearch(int[] a, int n, int key) {
int i = 0;
while (true) {
if (i == n)
return -1; // 검색 실패 (-1을 반환)
if (a[i] == key)
return i; // 검색 성공 (인덱스를 반환)
i++;
}
}
}
// a : 검색할 배열
// n : 배열의 크기
// key : 찾을 값
알고리즘 2
class MainClass {
static int seqSearch(int[] a, int n, int key) {
for (int i = 0; i < n; i++) {
if (a[i] == key)
return i;
return -1;
}
}
알고리즘 3
class MainClass {
static int seqSearchSen(int[] a, int n, int key) {
int i = 0;
a[n] = key;
while (true) {
if (a[i] == key)
break;
i++;
}
return i == n ? -1 : i;
}
}
◽ 앞선 알고리즘과는 다르게 입력할 배열의 요소 숫자보다 하나 더 큰 수만큼 배열을 생성한다.
◽ 배열의 마지막 인덱스에 찾고자 하는 값을 넣고, 배열을 끝까지 탐색한 후 i 값을 확인하여 탐색에 성공했는지 실패했는지를 구분짓는 "보초법"이라는 알고리즘이다.
◽ 시간 복잡도는 O(n)이다.
이진 검색
✔️ 요소가 오름차순 혹은 내림차순으로 정렬됐다는 가정하에 사용할 수 있는 알고리즘이다.
알고리즘 1
class MainClass {
// 요솟수가 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; // 검색 실패
}
}
◽ 시간 복잡도는 O(logn)이다.
Arrays.binarySearch
✔️ java.util.Arrays 클래스에서 제공하는 메서드
Arrys.binarySearch(x, key);
◽ 배열 x에서 키 값이 key인 요소를 검색
◽ 검색 성공 시 인덱스를 반환한다.
◽ 검색 실패 시 삽입 포인트를 x라고 할 때 - x - 1을 반환한다. 삽입 포인트는 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스이다.
'Data Structure' 카테고리의 다른 글
배열로 집합 만들기 (0) | 2021.12.13 |
---|---|
재귀 알고리즘 (0) | 2021.11.30 |
큐 (0) | 2021.11.29 |
스택 (0) | 2021.11.28 |
배열 (0) | 2021.11.22 |