검색(선형 검색, 보초법,이진 검색

선형 검색 

 

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

 

ex) 

import java.util.Scanner;

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

 

 

보초법 

 

- 선형검색의 비용을 반으로 줄여준다 

- 초법은 검색할 배열의 가장 끝에 검색할 값을 보초처럼 세워둔다

- 원래 배열에서 원하는 값을 찾지 못하면 미리 마지막에 세워둔 인덱스에서 멈춘다

- 반복문을 나왔을 때 인덱스의 값이 배열의 끝인지 아닌지를 확인하면 된다 

 

ex) 

import java.util.Scanner;

public class SeqSearchSen {
  
  static int seqSearchSen(int[] a, int n, int key) {
    int  i = 0;
    
    a[n] = key;
    //보초를 세워둠
    
    while (true) {
      if (a[i] == key)
        break;
      i++; //키값이 아닐경우 1씩 더해줌
    }
    return i == n ? -1 : i;
    //i가 n일때 값을 못찾은 것이므로 -1을 반환하고 아닐 경우 i 반환
  }
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    
    System.out.print("요솟수: ");
    int num =  stdIn.nextInt();
    int[] x = new int[num + 1];
    
    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 = seqSearchSen(x, num, ky);
    
    if (idx ==  -1)
      System.out.println("그 값의 요소가 없습니다.");
    else
      System.out.println(ky + "은(는) x["+ idx + "]에 있습니다.");
  }
}

 

 

이진 검색 

 

- 데이터가 키 값으로 이미 정렬(sort)가 되어 있다는 점

- 선형 검색보다 효율적이다

 

ex) 오름차순 배열을 이진검색 

import java.util.Scanner;

public class BinSearch {
  
  static int binSearch(int[] a, int n, int key) {
    int left  = 0;
    int right = n  -1;
    
    do {
      int mid = (left + right) / 2;
      if (a[mid] == key)
        return mid;
      else if (a[mid] < key)
        left = mid + 1;  //제일 작은 값을 중앙값보다 더 크게 함으로써 탐색 범위를 줄임 
      else
        right = mid - 1;  //제일 큰 값을 중앙값보다 작게 함으로써 탐색 범위를 줄임 
    } while ( left<= right); //계속 반복 
    
    return -1; //찾는 값이 없을 경우 -1을 return 
  }
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    
    System.out.print("요솟수: ");
    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.print       ("x[" + i + "]: ");
        x[i] = stdIn.nextInt();
      } while (x[i] < x[i - 1]); //오름차순으로 입력되지 않았을 때는 값을 다시 입력하도록 
    }
    
    System.out.print("검색할 값: ");
    int ky = stdIn.nextInt();
    
    int idx = binSearch(x, num, ky);
    
    if (idx == - 1)
      System.out.println("그 값의 요소가 없습니다.");
    else
      System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
  }
}