Hey_jinss

 * 1) 선형검색의 한계  선형검색은 무한루프를 통해 검사를 진행하므로 종료조건에 있어 비용이 든다.
 *  검색 실패, 검색 실패, 검색실패, 검색 성공 과 같은 식이다. 
 *  => 이 비용을 반으로 줄이는 방법이 보초법이다. 

 * 1) 2를 검색해서 성공하는 조건 2 5 3 4 [2]
 * 2) 5를 검색해서 실패하는 조건 0 2 4 1 [5]
 * 이와 같이 끝자리 수에 검색하고자 하는 값을 보초라고하는데, 원하는 값이 존재하지 않아도 보초값까지 검색하면 종료가 성립된다. 

 * 다시 말해 
 * #선형 검색 의 경우 : 
 *  int i = 0 으로 요솟수를 정의하고 
 *  while(true) {
 *  if(i==n)
 *  return -1; 
 *  if(a[i] == key)
 *  return 1; 
 * 과같이 첫번째 if문처럼 종료조건1을 달아야하는데, 이 과정이 필요가 없어지는 것이다. 
 * 따라서 보초는 반복문에서 종료 판단횟수를 2회에서 1회로 줄이는 역할을 한다. 

package chapter1;

import java.util.Scanner;

public class SeqSearchSen {


	
	
	//  요솟수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검색.
		static int seqSearchSen(int[] a, int n, int key) {
			
			int i = 0;

			a[n] = key;					// 보초를 추가 (a[요솟수] 니까 끝자리에 , 검색값을 한번 더 배치시킨다. 이것은 보초값을 가장 끝자리에 자리시키는 행위 

			while (true) {
				if (a[i] == key)		// 검색 성공!
					break;
				i++;
			}
			/*
			for(i=0; i<n; i++) {
				if(a[i] == key)
						break; 
			}*/
			
			// while이 반복되면, 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야 한다. 
			// 변수 i 값이 n 이면 찾은 값이 보초값이므로 검색실패를 나타내는 -1을 반환한다. 
			
			return 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];				// 요솟수 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);		// 배열x에서 값이 ky인 요소를 검색

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

package Search;

import java.util.Scanner;

public class BinSearch {

  static int binSearch(int[]a, int n, int key) { // 
  //int [] a == a라는 배열 ( 검색값이 입력되어있는 DB) 
  //int n == 요소수 
  //int key == 검색값 (사용자의) 
    
    int pl = 0; //검색값 첫번째 수 
    int pr = n-1;  //검색값의 마지막 수 
    
    do {
      int pc= (pl+pr)/2; //검색범위의 중위값  
          if(a[pc] == key) //중위값이 검색값이면 pc 반환  
            return pc; 
          else if (a[pc]<key) //중위값이 검색값보다 아래에 있으면 검색값 첫번째수가 현재 중위값의 위값 
            pl = pc+1;
          else pr = pc - 1;  //검색범위를 앞쪽 절반으로 좁힘 
    }   
    while (pl>= pr); //검색 마지막 범위가 첫번재범위보다 작으면 (검색이 완료가 되면) return -1 반환한다. 
    
    return -1; //검색 실패값 반환 
  }
  
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    
    Scanner scan  = new Scanner(System.in);
    //2. 요솟수가 num인 배열 생성  
    System.out.println("요솟수를 입력하세요");
    int num=scan.nextInt();
    int x[] = new int[num]; // 심화공부해야함 
    
    //2. DB값을 입력해주기 
    
    System.out.println("오름차순으로 입력하세요");
    
    System.out.println("x[0]");
    x[0] = scan.nextInt();
    //첫 요소 입력 
    //이미 요소수를 위에서 입력해주었으므로, 한정적으로 끝나게 되어있음.입력시에.
    for(int i=1; i<num; i++) {
    do {
    System.out.println("x["+i+"]=" );
    x[i] = scan.nextInt();
    }
    while (x[i]<x[i-1]); //앞의 요소보다 작으면 다시 입력 
  }
    
    System.out.println("검색값 입력하세요 [key]");
    int key = scan.nextInt();
    
    int idx = binSearch(x,num,key); 
    
    if(idx== -1) System.out.println("검색값 없음");
    else System.out.println(key+"는"+idx+"에 있음");
  }

}

오늘은 선형검색에 대해 알아보자 

 주소록을 검색한다고 가정 했을 때의 
 
 *  Searching 방식 : 
 *  1. 국적인 한국 사람을 찾는다.
 *  2. 나이가 21세 이상 27세  미만인 사람을 찾는다.
 *  3. 찾으려는 이름과 비슷한 이름의 사람을 찾는다. 
 
 *  데이터의 집합이 있을 때 검색만 하면되지! 라고 생각한다면 검색에 사용할 알고리즘은 계산 시간이 짧은 것을 선택      하면 되지만 데이터가 추가/삭제 등이 자주되는 경우라면, 검색 이외의 작업에 소요되는 비용을 판단해야 한다.
    따라서 필요한 요소를 평가하여 알고리즘을 선택한다. 

 *  1. 배열 검색 ( 검색은 빠르지만, 데이터 추가시에는 시간적인 비용이 많이 든다)
 *  2. 선형 리스트 검색
 *  3. 이진트리 검색 
 
 *  용도와 목적, 실행속도, 자료 구조 등을 고려하여 알고리즘을 선택한다. 

	//선형검색 
	
	/*검색 알고리즘 
	 * 	주소록을 검색한다고 가정 
	 * 
	 *  Searching 방식 : 
	 *  1. 국적인 한국 사람을 찾는다.
	 *  2. 나이가 21세 이상 27세  미만인 사람을 찾는다.
	 *  3. 찾으려는 이름과 비슷한 이름의 사람을 찾는다. 
	 *  
	 *  
	 *  
	 *  데이터의 집합이 있을 때 검색만 하면되지! 라고 생각한다면 검색에 사용할 알고리즘은 계산 시간이 짧은 것을 선택하면 되지만
	 *  데이터가 추가/삭제 등이 자주되는 경우라면, 검색 이외의 작업에 소요되는 비용을 판단해야 한다.
	 *  프 요소를 평가하여 알고리즘을 선택한다. 
	 *  1. 배열 검색 ( 검색은 빠르지만, 데이터 추가시에는 시간적인 비용이 많이 든다)
	 *  2. 선형 리스트 검색
	 *  3. 이진트리 검색 
	 *  
	 *  용도와 목적, 실행속도, 자료 구조 등을 고려하여 알고리즘을 선택한다. 
	 * 
	 * */
	
	//1. 메서드 (seqSearchEx) : 배열 a의 처음부터 끝까지/ n개의 요소를 대상으로, key값을 선형검색하고, 검색한 요소의 인덱스 반환 
	// 또한 값이 key인 요소가 여러개 존재할 경우 반환값은 검색과정에서 처음 발견한 요소의 인덱스가 된다.
	// 값이 key인 요소가 존재하지 않으면, -1 을 반환한다. 
	static int seqSearchEx(int [] a , int n, int key) {  // 테이블, n개 요소, 파라미터 값 
	int i = 0; 
	
	while (true) {
		if(i==n) 
			return -1; //검색 실패(-1을 반환) 
		
		if (a[i] == key) 
			return i ; //검색성공 (인덱스반환)
		i++;
	}
		
		
		}
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		
		//1. 배열 채우기 
		System.out.println("요솟수:");
		int num = stdIn.nextInt();
		int[] x = new int[num];
		
		
		for(int i = 0 ; i < num; i++) {
			System.out.println("x["+i+"]:");
			x[i] =stdIn.nextInt();
			
		} 
		
		//2. 검색값 입력 
		System.out.println("검색할 값 :");
		int ky = stdIn.nextInt();
		
		
		//3. 검색 메서드 실행 
		int idx = seqSearchEx(x, num, ky);
		
		//4. 결과 값 반환 
		if(idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"는 x ["+idx+"] 에 있습니다. " );
	}
	}