검색 알고리즘

- 검색 알고리즘 : 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘

 

선형검색 

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

package basic;

import java.util.Scanner;

public class SeqSearch {
    static int seqSearch(int[] a, int n, int 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(ky + "은(는) x[" + idx + "]에 있습니다.");
        }

    }
}

- 배열  a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색함

이진검색

- 전제조건: 데이터가 키 값으로 이미 정렬되어있다는 점

- 이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

- 찾을 key값을 정해두고, 배열의 끝 인덱스와 처음 인덱스의 중간 지점을 찾아서 해당 key값이 반 지점보다 낮거나 큼에따라 배열의 끝 인덱스와 처음 인덱스의 값을 변경하는 알고리즘.  중간 지점이 key값과 같으면 해당 중간 지점을 리턴한다.

- 이진 검색은 검색을 반복할때마다 검색 범위가 절반이 되므로 검색에 필요한 비교횟수의 평균값은 log n이다

package basic;

import java.util.Scanner;

public class BinSearch {

    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);

        System.out.println("요솟수 : ");
        int num = stdIn.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요.");

        System.out.print("x[0] : ");
        x[0] = stdIn.nextInt();

        for(int i=1;i<num;i++){
            do{
                System.out.println("x[" + i + "] : ");
                x[i] = stdIn.nextInt();
            }while (x[i] < x[i-1]);
        }

        System.out.println("검색할 값:");
        int ky = stdIn.nextInt();

        int idx = binSearch(x, num,ky);

        if(idx ==-1)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(ky+ "은(는) x[" + idx + "]에 있습니다.");
    }
}

Arrays.binarySearch에 의한 이진 검색

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

- Java.util.Arrays클래스의 binarySearch메서드

ex) static int binarySearch(Object[] a, Object key)

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

- 검색에 성공한 경우 일치하는 요소의 인덱스를 반환함 / 실패한 경우 삽입포인트를 x라 할때 -x-1을 반환함

package basic;

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

public class BinarySearchTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.println("요솟수:");

        int num = stdIn.nextInt();

        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요.");

        System.out.println("x[0] : ");

        x[0] = stdIn.nextInt();

        for (int i = 1; i < num; i++) {
            do {
                System.out.print("x[" + i + "]: ");
                x[i] = stdIn.nextInt();
            } while (x[i] < x[i - 1]);
        }

        System.out.println("검색할 값 : ");
        int ky = stdIn.nextInt();

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

        if (idx < 0)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");

    }
}