11.09.(수) Java-14: 선형검색, 이진검색

선형검색 (Sequential Search)

메소드를 이용해 검색처리하는 방법을 알아보자.

제목에서 알 수 있듯이 두가지 방법이 있는데, 먼저 선형검색을 알아보자.

선형검색은 다른 말로 순차검색이라고도 하는데, 말 그대로 배열의 처음부터 끝까지 하나하나 훑어가는 방법이다.

 

한 배열에 100개의 값이 들어있다고 하자. 만약 내가 찾고 싶은 값이 67번째 데이터일때, 선형검색은 0번부터 99번까지, 혹은 99번부터 0번까지 하나씩 들추면서 맞는지 아닌지 확인하는 방법이다.

public static int linearSearch(int num, int[] data, int value) {
    // for문으로 선형검색
    for(int i=0; i<num; i++) {
        if(data[i]==value) {	// 데이터를 찾았을 때 해당 index 리턴
            return i;
        }
    }
    return -1;	// 데이터를 못 찾았을 떄 -1 리턴
}

특징

배열의 형태나 규칙에 상관없이 사용이 가능하다.

하지만 온전히 노가다 방식이기 때문에, 데이터양이 증가할 수록 처리 시간이 길어진다.

 

이진검색 (Binary Search)

선형검색이 데이터 하나하나씩 훑고 가는 ,단순무식하지만 쉬운 방식이었다면, 이진검색은 조금 복잡하지만 똑똑한 방법이라고 할 수 있다.

이진검색은 데이터를 정렬시킨 후, 찾고자하는 값이 중간값보다 큰지 작은지를 판단해가며 검색범위를 좁히는 방법이다.

이는 선형검색에 비해서 엄청난 효율을 보여주는데, 이 효율성은 데이터양이 커질수록 더 극명하게 나타난다.

하지만 아무런 전제조건이 없는 선형검색과는 다르게 이진검색에는 전제조건이 붙는다. 앞서 말했듯이 배열 안의 데이터들이 정렬되어있어야한다.

이진검색을 시작하기에 앞서 무작위로 숫자를 뽑아서 배열에 넣은 후 크기순으로 정렬하는 방법을 알아보자.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
    // 데이터의 수 입력 받아서 1~100사이 난수를 생성 후 오름차순으로 정렬
    System.out.print("데이터 수 : ");
    int cnt = sc.nextInt();

    // 난수를 이용하여 1~100사이의 값을 cnt 만큼 생성하여 배열에 저장
    int arr[] = new int[cnt];
    for(int i=0; i<cnt; i++) {
        arr[i] = rand.nextInt(100)+1;
    }

    // 정렬 - 오름차순
    Arrays.sort(arr);
    System.out.println("정렬 : " + Arrays.toString(arr));
}

콘솔을 이용해 배열의 크기를 정하고, 그만큼 for문을 통해서 난수를 만들었다.

무작위로 생성된 값들을 가지고 있는 arr[] 배열을 Arrays.sort() 메소드를 이용하여 오름차순으로 정렬해주었다.

이제 이진검색 메소드를 만들어보자.

public static int binarySearch(int cnt, int[] arr, int inData) {	// 결과값의 index를 리턴
    int pl = 0;			// 시작위치 index
    int pr = cnt-1;		// 끝위치 index

    do {
        int pc = (pl+pr)/2;	// 중간위치 index
        if(inData==arr[pc]) {
            return pc;
        }else if(inData > arr[pc]) {	// 찾는 값이 중간위치의 값보다 클 때 
            pl = pc+1;			// 기존 중간위치 index를 새로운 시작위치로 설정
        }else if(inData < arr[pc]) {	// 찾는 값이 중간위치의 값보다 작을 떄 
            pr = pc-1;					// 기존 중간위치 index를 새로운 끝위치로 설정
        }
    }while(pl <= pr);	// 종료

    // 검색을 했는데 데이터가 존재하지 않을 때
    return -1;
}

binarySearch() 함수의 입력값으로 cnt (배열크기), arr (배열), inData (검색값)이 있다.

배열내의 값들의 번호표라고 할 수 있는 index값을 이용해서 첫번째 값과 마지막 값과 중간위치의 값을 구할 수 있다.

시작위치, 즉 0번 index를 pl(point left)로 정하고, 끝위치인 (배열크기-1)번 index를 pr(point right)로 정의했다.

do~while 반복문을 통해서 원하는 값을 찾아보자.

 

중간위치 index값 pc를 pl과 pr의 중간값으로 우선 구해주고,

int pc = (pl+pr)/2;	// 중간위치 index

inData(검색값)이 arr[pc] 과 일치하면 pc를 리턴한다.

if(inData==arr[pc]) {return pc;}

만약 일치하지 않는다면 크거나 작은 것이니 대소비교를 통해 큰쪽을 배제할지, 작은쪽을 배제할지 정하게 된다.

else if(inData > arr[pc]) {		// 찾는 값이 중간위치의 값보다 클 때 
        pl = pc+1;			// 기존 중간위치 index를 새로운 시작위치로 설정
    }else if(inData < arr[pc]) {	// 찾는 값이 중간위치의 값보다 작을 떄 
        pr = pc-1;			// 기존 중간위치 index를 새로운 끝위치로 설정
    }
}while(pl <= pr);	// 종료

크면 pc를 기준으로 왼쪽인 pl방향으로 배열의 절반을 배제한 후 pc의 한 칸 오른쪽에 위치한 배열값이 새로운 pl이 된다.

반대로 작다면 pc를 기준으로 오른쪽인 pr방향으로 데이터의 절반을 배제한 후 pc의 왼쪽 한칸에 위치한 데이터가 새로운 pr이 된다.

만약 검색값이 존재하지 않는다면 논리형 연산자 false에 해당하는 -1을 리턴하면 된다.

이 방식으로 배열을 절반씩 날려버리면 선형검색보다 훨씬 더 빠르고 효율적으로 검색값에 도달할 수 있다.

 

다시 실행메소드로 돌아가서 실행시켜보자.

// 찾을 값 입력
System.out.print("찾고 싶은 값 입력 : ");
int inData = sc.nextInt();	// NumberFormatException

// 이진검색 실행
int result = binarySearch(cnt, arr, inData);	// -1이면 없다
if(result==-1) {
    System.out.println(inData + "는 존재하지 않습니다.");
}else {
    System.out.println(arr[result] + "는 " + result + "번째 index에 있습니다.");
}

sc.close();