[JAVA] 검색 (1)

자료구조와 함께 배우는 알고리즘 입문 - 자바편

책 보면서 차근차근 공부하는 중

---

선형 검색

배열 검색의 종료 조건 2가지
1. 원하는 값을 찾지 못하고 배열의 끝을 마주한 경우
2. 원하는 값을 찾았을 경우
배열의 요솟수가 n개 일 때 조건 1,2를 판단하는 횟수는 평균 n/2

-> 비용을 반으로 줄이는 방법 : 보초법
검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장. 이 때 저장하는 값을 보초(sentinel)이라고 함

public static int seqSearchSen(int[] a, int n, int key){
	int i = 0;
    	a[n]=key; // 보초를 추가
        while(true){
        	if(a[i]==key) //검색성공!
     			break;
                i++;
        }
        return i==n?-1:i;
}

이진 검색

이 알고리즘을 적용하는 전제 조건은 데이터가 이미 정렬되어 있다는 것
Binary Search는 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
예시 ) 5 7 15 28 29 31 39 58 68 70 95 , key : 39
1. 중앙 요소인 31부터 검색
2. 검색 값인 39는 31보다 크니까, 검색 대상을 뒤의 5개로 좁힐 수 있음. 그리고 또 중앙요소를 살펴봄
=> 39 58 68 70 95 => 39 58로 줄일 수 있음

import java.util.Scanner;

public class Main {
    public static int binarySearch(int[] a,int n, int k){
        int first=0;
        int last=n-1;

        do{
            int middle = (first+last)/2;
            if(a[middle]==k){
                return middle;
            }
            // 중간 값이 우리가 찾고자 하는 값보다 작을 때
            else if(a[middle]<k){
            // 첫번째 인덱스를 중간 값 이후로 
                first=middle+1;
            }else{
            // 그게 아니라면 마지막 값을 중간 한 칸 앞으로 
                last=middle-1;
            }
        }while(first<=last);
        return -1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.print("요솟수 : ");
        int num = sc.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요.");
        for(int i=0;i<num;i++){
            System.out.print("x["+i+"] : ");
            x[i]=sc.nextInt();
        }

        System.out.print("검색할 값 : ");
        int key = sc.nextInt();

        int result = binarySearch(x,num,key);
        if(result==-1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(key+"은(는) x["+result+"]에 있습니다.");
        }
    }
}