JAVA 선형검색, 이진검색
자바의 검색 중에는 여러 가지 검색방식이 있지만, 선형 검색과 이진 검색에 대해 알아봅니다
1. 선형검색(LinearSearch)이란?
"데이터가 무작위로 놓여있는 즉, 정렬이나 어떠한 기준 없이 데이터가 놓여있을 경우, 데이터의 처음부터 원하는 값에 대해 순차적으로 검색하는 방법"
배열을 예를 들면 처음 인덱스부터 마지막 인덱스까지 검색범위를 정한 뒤에 검색하고자 하는 값을 대입하여 찾는 방법이 다. 단순하게 처음부터 끝까지 아무런 조건 없이 찾기만 하면 되니까 구현하기에는 편리하다.
하지만 데이터양이 많아지고 처음부터 데이터를 검색한다는 게 무작정 검색을 단순하게 한다는게 좋지는 않은 방법이다.
| (index) | 0 | 1 | 2 | 3 |
| (value) | 2 | 4 | 3 | 7 |
예를 들면 value=3이라는 값을 임의의 배열에서 선형 검색으로 찾는다면,
차례대로 index 0부터 찾으면서 찾고자 하는 value를 찾으면 되는 간단한 방식이다.
value를 찾게 되면 종료.
(데이터가 엄청 많으면 찾는 시간도 엄청 오래 걸릴 것입니다.)
public class Main {
public static void main(String[] args) {
int[] a = {1, 5, 24, 55, 12, 235, 234, 33,};
int key = 33;
int answer = arrSearch(a, key);
if (answer == -1) {
System.out.println("검색실패");
} else {
System.out.printf("배열의 %d번째에 있습니다", answer);
}
}
public static int arrSearch(int[] a, int value) { //배열a와 찾는값 value
for (int i = 0; i < a.length; i++) {
if (a[i] == value) {
return i + 1;
}
}
return -1;
}
arrSearch()의 메서드의 종료 조건은 2가지입니다.
1) 배열 a에서 검색하고자 하는 값을 찾았을 경우.
2) 배열 a에서 검색하고자 하는 값을 찾지 못했을 경우.
종료 조건이 2가지뿐이지만 검사비용이 많이 들지는 않지만, 종료 조건이 더더욱 많아지면, 검사비용이 많이 듭니다.
종료 조건 중에 1번을 충족하기 위해 검색을 하니까, 2번의 종료 조건을 없애서 검사비용을 줄이면 됩니다.
그럼 정리하면 무조건 검색 시에 찾고자 하는 값을 강제로 찾게 하면 됩니다.
보초 법을 이용하면 됩니다.
보초 법을 이용하기 위해서는 보초라는 뜻을 즉, 찾고자 하는 값을 배열의 마지막 인덱스에 넣어주고
배열을 선형 검색을 할 때 배열에 원하는 값이 없으면 어차피 무조건 배열의 마지막 부분에 값을 넣어주니까
무조건 찾게 되어 검사비용이 줄어들게 됩니다.
예를 들면, 밑에 처럼 배열이 주어지고 찾고자 하는 값이 7일 경우에는 배열에는 원하는 7의 값이 없다.
| (index) | 0 | 1 | 2 | 3 |
| (value) | 4 | 5 | 1 | 6 |
↓ 보초 법을 이용하면
| (index) | 0 | 1 | 2 | 3 | 4 |
| (value) | 4 | 5 | 1 | 6 | 7 |
이렇게 배열의 마지막 인덱스에 찾고자 하는 값(7)을 넣어준다. 그럼 어차피 무조건 찾게 된다?
그럼? 없어도 무조건 찾게 되는데 잘 못 된 거 아닌가(?) 생각이 들기도 했는데, 배열의 마지막에 찾고자 하는 값이 있으면 없는 것이다.
public static int arrSearch1(int[] a, int value) {
a[a.length - 1] = value;// 보초법을 사용하기위한 마지막 인덱스에 value값 설정.
int n = 0;
while (true) {
if (a[n] == value) {
break;
}
n++;
}
return n == a.length - 1 ? -1 : n + 1;보초 법을 적용한 코드입니다.
2. 이진 검색(BinarySearch)
이진(이분) 검색이란 순차 검색은 무조건 앞에서부터 검색하는 거와 달리 이진검색은 반으로 나누어 검색의 범위를 계속 좁혀서 찾는 방법입니다.(반으로 나눈다고 생각하면 될 듯..?)
하지만 이진 검색을 하기 위해서는 조건이 필요합니다.
선형 검색과는 달리 데이터가 오름차순이나 내림차순으로 정렬이 되어있거나 데이터가 정리가 되어 있어야합니다.
위에 같은 방식으로 검색범위를 줄여가며, 검색을 하는 방식이다.
public static int arrBiSearch(int[] a, int key) {
int f = 0; //배열의 첫번쨰 인덱스
int l = a.length - 1; //배열의 마지막 인덱스
do {
int m = f + l / 2; //배열의 중간 인덱스
if (a[m] == key) { //중간 인덱스값의 요솟값과 같은경우 .
return 1;//찾으면 1을 리턴
} else if (a[m] < key) { //중간 인덱스값의 요소값보다 클 경우
f = m + 1;//중간인덱스를 중간의 첫번째 인덱스로 교체
} else { //중간 인덱스값의 요소보다 작을 경우.
l = m - 1;
}
}
while (f <= l);
return -1; //검색실패시 -1를 리턴
}사람마다 로직은 다르게 코딩하겠지만, 거의 비슷한 방법으로 하지않았을까 생각이 듭니다.
자바에서도 이진검색을 지원하는 Arrays.binarySearch() 가 있습니다.
static메서드로 @notnull인 int[] 타입의 배열과 , key인 즉, 찾고자하는 int타입의 값을 매개변수로 받아
binarySearch0()가 int타입으로 return을 해줍니다.
위와 같은 로직으로 이진검색을 한다.
간단하게 보면 찾았을 경우에는 찾은값의 인덱스 값을 return(찾았을 경우에는 무조건 양수가 리턴이다).
찾지못했을 경우에는 mid값이 +1를 더해서 음수값을 return한다(못 찾았을 경우에는 무조건 음수가 리턴).
이렇게 선형, 이진 탐색에 대하여 알아보았습니다
Reference
자료구조로 배우는 알고리즘(do it)을 참고하여 작성하였습니다.