黑马程序员技术交流社区

标题: New灬狼的学习笔记--ArrayTest05 [打印本页]

---

作者: New灬狼    时间: 2016-1-8 22:22
标题: New灬狼的学习笔记--ArrayTest05
/**
        New灬狼
        2015年12月30日20:11:15
*/

/*
需求：
        定义一个功能，根据给定的数，检查数组中是否存在同样的数；
        因为遍历整个数组需要时间，为了提高效率，我们使用折半查找法。

思路：
        1，什么是折半查找法呢？假如从1--100之间猜一个数，先猜50,说这个数比50大；
        再猜的范围就缩小到了51--100，再取一个中间说猜，75，说这个数比75小；
        那么范围就变成了51--74，再取一个中间数，因为24/2=12，再用62去比较；
        直到找到这个数。
        2，因为是和数组中的元素比较，所以存在两种情况，一种是有的时候，返回该数的角标；一种是没有。
        3，因为上面不断改变范围的时候是有规律的，所以可以用循环去做。
注意：
        ！4，因为用给定的数和数组的数做比较，不断改变范围，所以要求数组必须是一个有序数组。
       

步骤：
        1，新建ArrayTest05.java；
        2，定义功能halfSearch；
        3，新建一个数组；排序；查找；检查功能是否正常。
*/

class ArrayTest05
{
        public static void main(String [] args)
        {
                int [] arr = {3,1,8,4,6,5,9,7,2};
                //先对数组从小到大排序
                java.util.Arrays.sort(arr);
                //查看排序
                display(arr);
                //查找给定的数，并把角标的数值赋值给half,以方便调用
                int half =halfSearch(arr,7);
                display(half);
                int half1 =halfSearch(arr,70);
                display(half1);       

                int h2 =halfSearch_2(arr,9);
                display(h2);
                h2 =halfSearch_2(arr,10);
                display(h2);
        }

        //定义函数halfSearch                返回值类型 int；参与运算的未知数，一个数组和一个给定的整数。
        public static int halfSearch(int [] arr,int key)
        {
                //数组最小角标min=0，最大角标max=arr.length-1；中间角标mid=(min+max)/2
                int min        =0,max = arr.length-1;
                int mid=(min+max)/2;
                //设置循环
                while (key !=arr[mid])
                {
                        //key比中间数大
                        if(key>arr[mid])
                                min=mid+1;
                        //key比中间数小
                        else if(key<mid)
                                mid=max-1;
                        //再次折半
                        mid=(min+max)>>1;
                        //如果最小角标超过最大角标，说明数组中没有这个数
                        if(min>max)
                                return -1;
                }
                return mid;                       
               
        }
        //halfSearch的第二种做法
        public static int halfSearch_2(int [] arr,int key)
        {
                int min=0,mid;
                int max=arr.length-1;
                //当满足折半条件时
                while (min<=max)
                {
                        mid=(min+max)>>1;
                        if (key>arr[mid])
                        {
                                min=mid+1;
                        }
                        else if (key<arr[mid])
                        {
                                max=mid-1;
                        }
                        else
                                return mid;
                }
                //如果循环停了还没有找到，就说明没有
                return -1;
        }


        //遍历数组 display
        public static void display(int[] arr )
        {
                System.out.print("数组中的元素是：\n{ ");
                for (int x=0;x<arr.length ;x++ )
                {
                        if(x!=arr.length-1)
                        {
                                System.out.print("["+x+"]="+(arr [x])+" ,");
                        }
                        else
                        {
                                System.out.println("["+x+"]="+(arr [x])+" }\n");
                        }
                }
        }
        //根据返回值，判断输出角标还是没有这个数
        public static void display(int x)
        {
                if (x<0)
                {
                        System.out.println("数组中没有这个数！");
                }
                else       
                        System.out.println("数组中有这个数，角标为： "+x);

        }

}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2