//数组查找
class SearchTest
{
        public static void main(String[] args)
        {
                //int[] arr = {2,5,8,4,6};
                int [] arr = {3,5,6,8,12};
                int index = halfSearch_1(arr,4);
                System.out.println("index="+index);
        }
        //将一个数插入到数组中，插入后还要保证数组的有序
        //折半查找，找出那个数应该对应的角标，折半查找数组必须是有序的
        public static int halfSearch_1(int[] arr,int key)
        {
                int min=0;
                int max=arr.length-1;
                while (min<max)
                {
                        int mid=(min+max)/2;
                        if(key>arr[mid])
                                min=mid+1;
                        else if(key<arr[mid])
                                max=mid-1;
                        else
                                return mid;
                }
                return min;//min的角标对应的就是要插入的位置

        }
        //折半查找
        public static int halfSearch(int[] arr,int key )
        {
                int min=0,max= arr.length-1,mid=(min+max)/2;
                while (key!=arr[mid])
                {
                        if (key>arr[mid])
                                min=mid+1;
                        else if (key<arr[mid])
                                max=mid-1;
                       
                        if (min>max)//目的值不存在，没找到
                                return -1;
                       
                        mid = (min+max)/2;
                       
                }
                //当循环的条件不满足时，不是找到了，就是不存在
                return mid;
        }
        /*
        public static int search(int[] arr,int key)
        {
                for (int x=0;x<arr.length ;x++ )
                {
                        if (key==arr[x])
                                return x;
                }
                return -1;

        }
        */
}

//数组查找
class SearchTest
{
        public static void main(String[] args)
        {
                //int[] arr = {2,5,8,4,6};
                int [] arr = {3,5,6,8,12};
                int index = halfSearch_1(arr,4);
                System.out.println("index="+index);
        }
        //将一个数插入到数组中，插入后还要保证数组的有序
        //折半查找，找出那个数应该对应的角标，折半查找数组必须是有序的
        public static int halfSearch_1(int[] arr,int key)
        {
                int min=0;
                int max=arr.length-1;
                while (min<max)
                {
                        int mid=(min+max)/2;
                        if(key>arr[mid])
                                min=mid+1;
                        else if(key<arr[mid])
                                max=mid-1;
                        else
                                return mid;
                }
                return min;//min的角标对应的就是要插入的位置

        }
        //折半查找
        public static int halfSearch(int[] arr,int key )
        {
                int min=0,max= arr.length-1,mid=(min+max)/2;
                while (key!=arr[mid])
                {
                        if (key>arr[mid])
                                min=mid+1;
                        else if (key<arr[mid])
                                max=mid-1;
                       
                        if (min>max)//目的值不存在，没找到
                                return -1;
                       
                        mid = (min+max)/2;
                       
                }
                //当循环的条件不满足时，不是找到了，就是不存在
                return mid;
        }
        /*
        public static int search(int[] arr,int key)
        {
                for (int x=0;x<arr.length ;x++ )
                {
                        if (key==arr[x])
                                return x;
                }
                return -1;

        }
        */
}