1일 1코딩

* 데이터 검색 시 사용 목적, 속도, 비용 등을 고려해 알고리즘을 선택해야 함.

 

/**
 * 선형검색
 * 배열에서 순차적으로 검색하는 유일한 방법
 * 
 * 무한 루프 구현
 * 1. while(true){}
 * 2. for( ; ; ){}
 * 			for문에서 제어식을 생략하면 1이 지정된것으로 봄.
 * 3. do{
 *    }while(true);
 *    	코드를 보고 바로 무한루프인 것을 알 수 없기때문에 권장 안함.
 *    
 *   해당 코드에서 종료조건: i==n이 성립하는 경우 
 *   				  a[i]==key가 성립하는 경우 
 *   
 *   요솟수가 n일 때 종료조건을 검사하는 비용: - 배열에 값이 없을 경우 1: n+1회 2: n회
 *   			(종료조건 판단횟수)	    - 평균 n/2회
 *   
 */		
package chap03;
import java.util.Scanner;
public class SeqSearch {
	
	//요솟수가 n인 배열a에서 key와 같은 요소를 선형검색합니다.
	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(int i=0; i<n;i++) { // 배열a의 앞쪽 n개의 요소에서 key와 같은 요소를 선형 검색
			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.printf("x[%d] :	",i);
			x[i]=stdIn.nextInt();
		}
		System.out.print("검색할 값 : ");
		int ky=stdIn.nextInt();
		
		int idx=seqSearch(x,num, ky); //배열 x에서 키 값이 ky인 요소를 검색
		
		if(idx==-1)
			System.out.println("그 값의 요소가 없습니다.");
		else System.out.println(ky+"은(는) x["+idx+"]에 있습니다.");
	}
}

 

---

이진 검색

package chap03;
import java.util.Scanner;
//이진 검색
//요소가 정렬되어 있어야 한다.
//횟수: 대략 log(n-1)회
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);  //종료조건2(검색할 범위)을 검사 존재할 경우만 do문 실행
		
		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]; //요솟수가 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.println("검색할 값 : ");  int ky=stdIn.nextInt(); 
		
		int idx=binSearch(x, num, ky); //배열 x에서 키값이 ky인 요소를 검색
		
		if(idx==-1) System.out.println("그 값의 요소가 없습니다.");
		else System.out.printf("%d은(는) x[%d]에 있습니다.",ky,idx);
		
		
	}
}