선형(순차) 탐색(Linear Search)

선형(순차) 탐색(Linear Search)은 자료를 탐색하는데 가장 무식하면서 이해하기 쉬운 알고리즘(algoritm) 이다.

선형(순차)탐색은 일종의 부르트포스(Brute Force)의 한 예이기도 한데 왜 무식하냐 하면 특정 자료를 찾기위해서 모든 자료를 뒤져봐야 알기 때문이다. 

찾는 것이 일찍나오면 그나마 다행인데 모든 자료 끝까지 뒤질때까지 안나오는 worst case 인경우 성능이 O(N)이다.

 

위 그림을 보면 더 이해하기 쉬운데 리스트  = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 } 에서 33을 찾기위해 처음부터 마지막 까지 같은 값이 있는지 하나씩 비교해가면서 찾는 것이다. 

코드 구현도 매우 간단한데 함수의 확장성을 고려해서 점진적으로 발전시켜 나가겠다.

 

 

 
int []arr = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44};
 
int key = 33 ;
int index = -1; //
for(int i = 0 ; i < arr.length ; i++) {
    if(arr[i] == key) { // 순차적으로 값을 비교해가면서 같은 값이 있는지 확인.
        index = i;
        break;
    }
}
 
if(index < 0) System.out.println("Not Found");
else System.out.println("Index = " + index);

 

 

위 코드는 정상적으로 잘 작동한다. 하지만 선형검색을 여기서만 사용하지 않고 다른곳에서 사용할 수 있으니 함수로 빼는게(extract method refactoring) 좋겠다. 

public class Main {
 
// 함수로 추출
    public static int linearSearch(int []arr, int key) {
        int index = -1; //
        for(int i = 0 ; i < arr.length ; i++) {
            if(arr[i] == key) {
                index = i;
                break;
            }
        }
        return index;
    }
 
    public static void main(String[] args) throws IOException {
 
 
        int []arr = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44};
 
        int key = 33 ;
        int index = linearSearch(arr, key); //
        if(index < 0) System.out.println("Not Found");
        else System.out.println("Index = " + index);
        
    }
 
}

 

타입이 integer 만 허용되니 다른 타입(type)에도 알고리즘을 적용할 수 있게 generic 으로 변경해보자.

 

 
public static <T>
    int linearSearch(T []arr, T key) {
    int index = -1; //
    for(int i = 0 ; i < arr.length ; i++) {
        if(arr[i] == key) {
        index = i;
        break;
        }
    }
    return index;
}

 

 

왜냐하면 자바에서 객체를 == 로 비교하는것은 레퍼런스를 비교하는것이지 값이 같은지 비교하는것이 아니다. 

따라서 객체의 값이 일치하는지 판단하기위해 별도의 Comparator 함수인터페이스를 제공하여 작성해보자.

 

public class Main {
 
    public static <T>
    int linearSearch(T []arr, T key, Comparator<? super T> c) {
        int index = -1; //
        for(int i = 0 ; i < arr.length ; i++) {
            if(c.compare(arr[i], key) == 0) {
                index = i;
                break;
            }
        }
        return index;
    }
 
    public static void main(String[] args) throws IOException {
 
 
        String []arr = { "10", "14", "19", "26", "27", "31", "33", "35", "42", "44"};
 
 
        String key = new String("33") ;
        int index = linearSearch(arr, key, (a, b) -> a.compareTo(b)); //
        if(index < 0) System.out.println("Not Found");
        else System.out.println("Index = " + index);
 
 
    }
 
 
}
 

 

 

이제 객체가 서로 동일한지 판단하는 메소드만 Comparator 함수인 compare에 를 적절히 작성하면 어떤 객체타입이던 적용가능하게 되었다.