[20210930] 점프(블록) 검색 알고리즘

package Practice;

import java.util.Scanner;

public class JumpSearch {
   public static void main(String[] args){
	   Scanner sc = new Scanner(System.in);
		System.out.println("배열의 크기를 입력하세요.");
		
		int size = sc.nextInt();
		int[] arr = new int[size];
		
		for (int i=0; i<arr.length; i++) {
			System.out.println("arr[" + i + "]에 해당하는 숫자를 입력하세요");
			arr[i] = sc.nextInt();
		}
		
		System.out.println("찾으려는 숫자를 입력하세요.");
		int x = sc.nextInt();
		
        int result = search(arr, x);
        System.out.println(result == -1 ? x + "은(는) 존재하지 않습니다." : "인덱스 : " + result);

        x = 20;
        result = search(arr, x);
        System.out.println(result == -1 ? x + "은(는) 존재하지 않습니다." : "인덱스 : " + result);
        
        sc.close();

    }

    public static int search(int[] arr, int x){
        int leng = arr.length;

        // 점프(블록) 사이즈 지정
        int jump = (int)Math.floor(Math.sqrt(leng));

        // prev_idx는 이전 jump 위치의 index를 의미, 현재와 이전의 사이가 바로 찾고자 하는 데이터가 있는 구간임
        int prev_idx = 0;

        // 전체 배열 길이와 jump 위치 중 더 작은 값을 우선하여 현재 탐색 위치 지정
        int curr_idx = Math.min(jump, leng)-1;
        while(arr[curr_idx] < x){
            prev_idx = curr_idx;
            curr_idx += jump;
            if(prev_idx >= leng){
                return -1;
            }
        }

        // 구간 내 선형 탐색 수행
        while(prev_idx <= curr_idx){
            if(arr[prev_idx] == x){
                return prev_idx;
            }
            prev_idx++;
        }
        return -1;
    }
}