선형 검색과 이진 검색

(배열 )선형 검색

요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색

import java.util.Scanner;

public class LinearSearch {

    static int seqSearch(int[] a, int n, int key) {
        //요솟수가 n인 배열 a 에서 key와 값이 같은 요소를 선형 검색
        int i = 0;

        while(true) {
            if(i == n) {
                return -1;  //실패
            }
            if(a[i] == key) {
                return i;   //성공
            }
            i++;
        }
        
//        for(int i=0; i<n; i++) {
//            if(a[i] == key) {
//                return i;
//            }
//            return -1;
//        }
    }

    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<num; i++) {
            System.out.print("x[" + i + "]:");
            x[i] = stdIn.nextInt();
        }

        System.out.print("검색할 값: ");
        int ky = stdIn.nextInt();
        int idx = seqSearch(x, num, ky);

        if(idx == -1) {
            System.out.println("요소가 없음");
        } else {
            System.out.println("x[" + idx + "]에 있음");
        }
    }
}

 

위 코드는 배열의 처음부터 끝까지 모두 검색한 후 key로 주어진 수가 발견되는 즉시 인덱스 값을 반환한다. 만약 key 값이 존재하지 않는다면 배열의 모든 길이를 검색한 후 -1을 반환한다. 

내가 만약 배열의 끝이 아닌 7번째 인덱스까지만 검색하고 싶다면 보초법을 사용하면 된다.

//a[0] ~ a[6] 있을 때 a[7]에 key 값을 넣고 반환하는 것

보초법을 사용하려면 위 코드에서 보초를 추가하고 배열의 길이만 조정하면 된다.

if(i == n) //종료 조건은 필요없다. 보초까지만 검색

a[n] = key; //보초까지 검색

while(true) {
	if(a[i] == key)
    	break;
    i++;
}
return i == n ? -1 : i;

int[] x = new int[num + 1];	//요소수가 1 증가한다.

---

(배열) 이진 검색

이진 검색의 전제 조건은 데이터가 키값으로 이미 정렬(sort)되어 있다는 것. 선형 검색보다 빠르다.

5

7

15

28

29

31

39

58

68

70

만약 위와 같은 배열이 있다면 중앙에 위치한 요소를 검색하고 찾고자 하는 값이 중앙 요소보다 크다면 검색 대상을 뒤쪽으로 좁힌다. 이 과정을 반복해서 원하는 값을 검색하는 방법이다.

import java.util.Scanner;

public class BinarySearch {
    
    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;
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        int num = stdIn.nextInt();
        int[] x = new int[num];
        
        x[0] = stdIn.nextInt();
        
        for(int i=0; i<num; i++) {
            do {
                x[i] = stdIn.nextInt();
            } while (x[i] < x[i - 1]);  //바로 앞의 요소보다 작으면 다시 입력
        }
        
        int ky = stdIn.nextInt();
        
        int idx = binSearch(x, num, ky);
        
        if(idx == -1)
            System.out.println("요소가 없음");
        else 
            System.out.println(idx + "에 있음");
    }
}

Arrays.binarySearch

자바는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다.

오름차순으로 정렬된 배열 a를 가정하고 같이 key인 요소를 이진 검색한다.

자료형에 따라 9가지 방법으로 오버로딩되어 있다.

• static int binarySearch(Object[] a, Object key)
• static <T> int binarySearch(T[] a, T key, Comparator <? super T> c)

//검색에 실패한 경우
int[] arr = {5, 7, 15, 28, 29, 32, 39, 58, 68, 72};
//39 검색 성공 -> 인덱스(6) 반환
//31 검색 실패 -> 인덱스(4),(5)사이에 위치 삽입 포인트(5) = -6 반환
//95 검색 실패 -> 삽입 포인트 배열의 길이 10 = -11 반환

int idx = Arrays.binarySearch(x, ky);

---

클래스 메서드와 인스턴스 메서드

인스턴스 메서드(비정적)는 static을 붙이지 않고 선언한 메서드이고, 클래스형의 개별 인스턴스에 속한다. 클래스 메서드(정적)는 static을 붙여 선언한 메서드이고, 특정 인스턴스에 속하지 않는다.

//아이디를 부여하는 클래스
class Id {
	private static int counter = 0;	//id를 몇 개 부여했는지 저장(클래스 변수)
    private int id;
    
    public Id() { id = ++counter; }	//생성자
    
    public static int getCounter() { return counter; }	//counter 반환하는 클래스 메서드
    
    public int getId() { return id; }	//아이디를 반환하는 인스턴스 메서드
}

---

자연 정렬

binarySearch 메서드에 배열과 키값을 전달하는 간단한 방법으로 검색할 수 있는 이유는 String 클래스가 Comparable<T> 인터페이스와 compareTo 메서드를 구현하고 있기 때문이다.

문자열 정렬	자연 정렬
텍스트1.txt 텍스트10.txt 텍스트100.txt 텍스트2.txt 텍스트21.txt	텍스트1.txt 텍스트2.txt 텍스트10.txt 텍스트21.txt 텍스트100.txt

둘 다 정렬은 되있지만 왼쪽은 자연스럽지 않다. 인간이 보기에 오른쪽이 자연스럽다.(자연 정렬)

//자연 정렬을 하려면 다음과 같은 패턴으로 클래스를 정의

class A implements Comparable<A> {
	//field, method
    public int compareTo(A c) {
    	//this가 c보다 크면 양의 값 반환
        //this가 c보다 작으면 음의 값 반환
        //this가 c와 같으면 0 반환
    }
    
    public boolean equals(Object c) {
    	//this가 c와 같으면 true 반환
        //this가 c와 같지 않으면 false 반환
    }
}

자연 정렬이 되지 않은 배열에서의 검색은 제네릭 메서드를 사용한다.

static <T> int binarySearch(T[] a, T key, Comparator <? super T> c)

package java.util;

public interface Comparator<T> {
	int compara(T o1, T o2);
    boolean equals(Object obj);
}

객체의 대소 관계를 판단하는 comparator를 사용자가 직접 구현하려면 Comparator 인터페이스를 구현한 클래스를 정의하고 그 클래스형의 인스턴스를 생성해야 한다. 그 후 매개변수로 전달된 두 객체의 대소 관계를 비교하여 그 결과를 아래의 값으로 반환하는 compare메서드를 구현하면 된다.

import java.util.Comparator;

class X {
	public static final Comparator<T> COMPARATOR = new Comp();
    
    private static class Comp implements Comparator<T> {
    	public int compara(T d1, T d2) {
		//d1이 d2보다 크면 양수 변환
		//d1이 d2보다 작으면 음수 변환
		//d1이 d2 같으면 0 변환
        }
    }
}

---

제네릭스

처리 대상의 자료형에 의존하지 않도록 클래스(인터페이스)를 구현하는 기능이다. 제네릭 클래스는 자료형에 의존하지 않기 때문에 범용으로 사용할 수 있다. 

• 대문자 1개 사용
• 컬렉션 내부 요소의 자료형 E
• Map 내에 키와 값의 자료형 K V
• 일반적 자료형 T
• <? extends T> 클래스 T의 하위 클래스를 전달 받음
• <? super T> 클래스 T의 상위 클래스를 전달 받음

class GenericClassTest {

	static class GenericClass<T> {
    	private T xyz;
        GenericClass(T t) {
        	this.xyz = t;
        }
        T getXyz() {
        	return xyz;
        }
    }
    
    public static void main(String[] args) {
    	GenericClass<String> s = new GenericClass<String>("ABC");
        GenericClass<Integer> n = new GenericClass<Integer>(15);
        
        System.out.println(s.getXyz());	//ABC
		System.out.println(n.getXyz());	//15
    }
}