package TwentyOne_Challenge;

public class DayFive {
    public static void main(String[] args) {
        int []a={3,38,5,44,15,36,26,27,2,47,46,4,19,50,48};
        sort(a);
        System.out.print("递增序列如下：");
        for (int i = 0; i <a.length ; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        int result1=Search(a,15);
        int result2=Search(a,666);
        System.out.println("查找15的结果为："+result1);
        System.out.println("查找666的结果为："+result2);
    }
    //折半查找法，找到返回其下标，找不到返回失败标志：-1
    private static int Search(int a[],int key){
        //left,right表示左右区间的下标
        int left=0,right=a.length-1;
        //循环终止条件为左右区间发生交错
        while(left<=right){
            //取出中间元素的下标，下面的下法是为了防止数据量较大时发生溢出
            int mid=(right-left)/2+left;
            if(a[mid]==key){
                return mid;
            }else if(a[mid]<key){
                //继续在右半区间找
                left=mid+1;
            }else {
                //继续在左半区间找
                right=mid-1;
            }
        }
        //如果循环结束还未触发return语句说明查找失败
        return -1;

    }
   //使用选择排序法先将数组变成递增有序的序列
    private static void sort(int a[]){
        for(int i=0;i<a.length-1;i++){
            int min=i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[min]){
                    min=j;
                }
            }
            if(min!=i){
                int temp=a[min];
                a[min]=a[i];
                a[i]=temp;
            }
        }

    }

}