배열 검색 알고리즘 (선형 검색, 이진 검색)

• 검색 알고리즘 고르는 법

 배열에서 검색을 하는 경우 보통 검색 속도가 빠른 알고리즘을 선택한다. 하지만 검색과 더불어 데이터를 추가, 삭제하는 작업이 필요한 경우 데이터의 추가, 삭제에 필요한 비용도 고려하여 알맞은 알고리즘을 골라야 한다. 따라서 어떤 목적을 이루기 위해 알고리즘을 선택한다면 종합적인 요소를 잘 고려해서 선택해야 한다.

 

• 선형 검색

선형 검색이란 원하는 값을 찾을 때까지 맨 앞부터 순서대로 검색하는 방법이다. while문으로 구현하면 다음과 같다.

public class Main {
    static Integer line(int key, int[] a){
        int i = 0;
        while(true){
            if(i==a.length) return -1; // i가 a의 index를 넘어선 경우 검색 실패로 -1 반환
            if(a[i]==key) return i; // index가 i 일때 검색에 성공한 경우 i 반환
            i++;
        }
    }

    public static void main(String[] args) {
        int[] a = {3,5,8,3,6,9,9,2,4,7};
        int key = 9;
        int ans =line(key,a);
        if(ans==-1){
            System.out.println("검색에 실패하였습니다.");
        }else{
            System.out.println("찾는 값은 a배열의 "+ans+"번째 index에 위치합니다.");
        }
    }
}

 

찾아야 하는 값인 key값과 검색 대상인 배열 a를 line함수에 넣으면 a[0]부터 a[j]까지 순서대로 key값과 비교를 한다.(여기서 j = 배열의 마지막 index로 이번 예제에서는 9이다.) 만약 도중에 배열의 요소와 key 값이 같은 것을 찾으면 요소의 index 값을 return한다. 그러나 index값을 뜻하는 i값이 j를 넘어서 j+1이 된다면 i==a.length의 조건에 걸려 -1을 return하고 검색은 실패하게 된다. 따라서 -1을 return하면 검색 실패 문구를, 양수인 index를 return하게 되면 검색 성공 문구와 key 값이 들어있는 배열의 index를 출력하게 된다. 

 

 이렇게 while문을 이용하면 반복할 때마다 2번의 if 조건 판단을 수행해야한다. 하지만 조건 판단을 1번으로 끝낼 수 있는 방법이 2가지 있다. 

 

  1. 보초법

 이는 while문을 사용하는 대신 보초를 세우는 방법이다. 보초를 세우는게 뭔지 아직 감이 안 잡힐 테니 먼저 보초 세우는 방법을 알아보자. 우선 보초를 세우기 위해 배열에 자리 1개가 더 필요하므로 배열의 크기를 +1 해준다. 그리고 +1 해준 자리에 우리가 찾고 싶은 key값을 대입한다. 이렇게 보초를 세우면 if 조건문을 1번만 만들어도 된다. if 조건문을 a[i]==key 1개만 사용하고 만약 배열a에 key값이 없어 찾지 못한 경우에도 마지막 보초가 key값이어서 조건문을 통해 반드시 반복문을 탈출할 수 있다.  

import java.util.Scanner;
public class Main {
    static Integer line(int key, int[] a){
        int i = 0;
        while(true){
            if(a[i]==key) return i; // index가 i 일때 검색에 성공한 경우 i 반환
            i++;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        int key = sc.nextInt();
        for(int i=0; i<n;i++){
            a[i]=sc.nextInt();
        }
        a[n]=key;
        int ans =line(key,a);
        if(ans==n){
            System.out.println("검색에 실패하였습니다.");
        }else{
            System.out.println("찾는 값은 a배열의 "+ans+"번째 index에 위치합니다.");
        }
    }
}

  2. for문 사용

 while문을 보초까지 세워가며 쓰고싶지 않다 하면 for문을 이용해도 된다. 이는 구현이 더 쉽고 간단하므로 자주 쓰인다.

내용은 쉬우므로 코드를 보고 이해하자.

import java.util.Scanner;
public class Main {
    static Integer line(int key, int[] a){
        for (int i=0; i<a.length;i++){
            if(a[i]==key) return i; // index가 i 일때 검색에 성공한 경우 i 반환
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int key = sc.nextInt();
        for(int i=0; i<n;i++){
            a[i]=sc.nextInt();
        }
        int ans =line(key,a);
        if(ans==-1){
            System.out.println("검색에 실패하였습니다.");
        }else{
            System.out.println("찾는 값은 a배열의 "+ans+"번째 index에 위치합니다.");
        }
    }
}

 i가 index값을 넘어가면 자동으로 for문이 종료되기 때문에 굳이 반복문을 탈출하기 위해 조건문을 하나 더 만들 필요가 없고 for문이 끝날 때까지 못 찾으면 그냥 -1을 return하는 방식으로 간단하게 만들면 된다.

 

 선형검색은 배열의 크기가 N개일 때 최악의 경우 N개를 다 뒤져야 하므로 시간복잡도는 O(N)이다.

 

• 이진 검색

 두번째로 이진 검색이 있다. 이진 검색은 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 간단하게 설명하면 현재 배열의 가운데에 위치한 값을 key 값과 비교하는데 결과에 따라 3가지 방법으로 이어진다.

   

   1) 가운데값 = key : 가운데값의 index 출력 (검색 성공)

   2) 가운데값 > key : 첫 번째부터 가운데값의 앞에 값까지 범위를 좁히고 다시 가운데값을 정하여 위 과정을 반복한다.

   3) 가운데값 < key : 가운데값 다음값부터 마지막값까지 범위를 좁히고 다시 가운데값을 정하여 위 과정을 반복한다.

 

이렇게 3가지 방법으로 계속 이어나가다 결국 가운데값 = key 인 경우가 나온다면 검색에 성공한 것이다. 하지만 마지막까지 가운데값이 key값과 다르다면 검색은 실패하게 된다. 코드를 보자.

import java.util.Scanner;

public class Main {
    static Integer binary(int key, int[] a, int pl, int pr){
        // pl = 검색 범위 중 가장 왼쪽 값 ,  pr = 검색 범위 중 가장 오른쪽 값'
        while(pl<=pr){  // 검색 실패 조건
            int pc = (pl+pr)/2; // pc = 검색 범위 가운데값 (소수점은 버린다.)
            if(key == a[pc] ) return pc; // 검색 성공
            else if(key < a[pc]) pr= pc-1; // 범위 변경 : a[pl]<= key < a[pc]
            else pl = pc+1; // 범위 변경 : a[pc]< key <= a[pr]
        }
        return -1; // 검색 실패
    }

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0; i<n ;i++){
            a[i]=sc.nextInt(); //요소는 오름차순 or 내림차순으로 입력
        }
        int key = sc.nextInt();
        int ans = binary(key, a,0,n-1);
        if(ans==-1){
            System.out.println("검색에 실패하였습니다.");
        }else{System.out.println("검색 결과 key 값은 a배열 index = "+ans+" 에 있습니다.");}
    }
}

 

 검색범위 내의 가장 첫번째값인 pl과 검색범위 내의 가장 마지막 값인 pr을 통해 검색범위 내의 가운데 값 pc를 구한다.(소수점은 버림) 그리고 위에서 말한대로의 반복을 통해 검색을 반복한다. 만약 검색범위가 1개가 남고 그마자도 key값과 다르면  pl값이 pr값보다 커진다. 이 순간이 검색에 실패한 경우이고 이땐 while문을 빠져나가 -1을 return한다.

 

 이진 검색은 사실 위의 예시처럼 메서드를 따로 구현할 필요가 없다. Arrays.binarySearch(배열, key값)으로 검색이 가능하다.  Arrays.binarySearch()를 이용하면 배열 요소의 자료형에 관계없이 사용할 수 있는 장점도 있다.

 만약 Arrays.binarSearch()를 이용하여 검색에 성공하면 해당 인덱스를 반환하고 배열내 요소들이 key값과 여러개 중복된다면 아무거나 먼저 반환한다.(순서가 정해지지 않음) 그러나 만약 검색에 실패할 경우 key값이 있어야할 위치를 추정할 수 있는 값을 x라 하면 -x-1을 return한다. 만약 x값이 0보다 작다면 배열의 크기값이 된다. 이해하기 쉽게 예시를 들면 만약 배열의 요소들이 1, 3, 5, 7, 9, 11, 13 이렇게 되어있고 key값이 4라고 하면 저음 pc=3 a[pc]=7이 되고 다음 루틴에서 pl=0 pr=2로 pc=1이 된다. a[pc]=3<key 이므로 pl=2,pr=2가 되고 a[pl]=a[pr] > key = 4이므로 검색에 실패한다. 하지만 굳이 key값이 있어야 할 곳을 추정해본다면 a[3]=5의 왼쪽인 a[2]가 되고 따라서 x=2이므로 -x-1=-3을 return 한다. 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0; i<n ;i++){
            a[i]=sc.nextInt(); //요소는 오름차순 or 내림차순으로 입력
        }
        int key = sc.nextInt();
        int ans = Arrays.binarySearch(a,key);
        if(ans<0){
            System.out.println("검색에 실패하였습니다.");
        }else{System.out.println("검색 결과 key 값은 a배열 index = "+ans+" 에 있습니다.");}
    }
}

 

 이진 검색의 시간복잡도는 O(logN)으로 선형 검색보다 훨씬 빠른 것을 알 수 있다. 그래서 보통 오름차순, 내림차순이면 선형 검색보다 이진 검색을 많이 쓴다.