검색(Search)

선 요약

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색 수행
2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색 수행
3. 해시법 : 추가, 삭제가 빈번한 데이터 모임에서 빠른 검색 수행
   1. 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
   2. 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

선형 검색(Linear Search)

• 직선으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 맨 앞부터 순서대로 요소 검색하는 방법, sequential search라고도 불린다.
• 조건
  • 조건 1. 원하는 키 값을 만나 검색 중단
  • 조건 2. 원하는 키 값을 만나지 못하고 전체 검색 후 종료
• 위 조건을 판단하는 횟수는 평균 n/2회

import java.util.Scanner;

public class Test1 {

    public static void main(String[] args) {

        Scanner stdIn = new Scanner(System.in);

        System.out.print("length : ");

        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("number to search : ");
        int key = stdIn.nextInt();

        int idx = SeqSearch.seqSearch(x, num, key);

        System.out.println(idx);

    }
}

class SeqSearch
{
    static int seqSearch(int[] a, int n, int key)
    {
        int i = 0;

        while(true) {
            if(i == n) {
                return -1; // 전체 검색하고 못 찾으면 -1 반환
            }

            if(a[i] == key) {
                return i; // 찾으면 인덱스 반환
            }
            i++;
        }
    }

		// for문으로 구현 시
		static int seqSearchUsingFor(int[] a, int n, int key) 
		{
		    for(int i = 0; i < n;i++) {
		        if(a[i] == key) {
		            return i;
		        }
		    }
		
		    return -1;
    }
}

보초법(sentinel method)

• 2개의 조건을 검사하는 비용을 50%으로 줄이는 방법
• 방법
  • 대상이 될 배열보다 사이즈가 1개 더 큰 배열을 만들고 마지막에 찾을 값을 넣는다.

// int[] a는 검색하고자 하는 대상들이 들어있는 원래 배열보다 1큰 배열이어야 함
static int seqSearchWithSentinel(int[] a, int n, int key)
{
    int i = 0;

    a[n] = key; // 마지막에 더해진 공간에 보초값(key) 추가
    while(true) {
        if(a[i] == key) // 조건이 이전과 달리 1번만 들어감
            break;
        i++;
    }
    return i == n ? -1 : i; // 마지막까지 검색했으면 -1 리턴
}