黑马程序员技术交流社区

标题: 在有序和无序数组中查询一个数的问题 [打印本页]

---

作者: 汪显晟    时间: 2013-9-20 21:20
标题: 在有序和无序数组中查询一个数的问题


class SelectArray {
        public static void main(String[] args) {
                int[] arr = {33,22,11,66,55,44};                        //无序数组
                //System.out.println(getIndex(arr,88));
                int[] arr2 = {11,22,33,44,55,66,77};
                System.out.println(getIndex3(arr2,88));
        }
        //无序的数组查找
        public static int getIndex(int[] arr,int key) {
                for (int x = 0;x < arr.length; x++ ) {
                        if (key == arr[x]) {
                                return x;
                        }
                }
                return -1;
        }
        //有序的数组二分查找
        public static int getIndex2(int[] arr,int key) {
                int min = 0;                                               //定义变量记录最小角标值
                int max = arr.length - 1;                              //定义变量记录最大角标值
                int mid = (min + max) / 2;                     //求出中间角标值

                while (key != arr[mid]) {                            //当查找的值不等于中间角标值,开始循环
                        if (key < arr[mid]) {                              //传入的值小于了中间角标值
                                max = mid - 1;                              //最大角标变化
                        }else if (key > arr[mid]) {                //传入的值大于了中间角标值
                                min = mid + 1;                           //最小角标变化
                        }
                        mid = (min + max) / 2;                //无论min还是max改变,中间角标值都要随之改变
                        if (min > max) {                        //当最小角标值大于了最大角标值,就没有折半的可能了,返回-1
                                return -1;
                        }
                }

                return mid;
        }

        //二分查找法的第二种做法
        public static int getIndex3(int[] arr,int key) {
                int min = 0;                                       //定义变量记录住最小的角标值
                int max = arr.length - 1;                       //定义变量记录住最大角标值
                while (min <= max) {                           //如果最小的角标值小于最大角标值就可以进行折半了
                        int mid = (min + max)/2;              //求出中间角标值
                        if (key < arr[mid]) {                        //判断传入的值如果小于中间角标值
                                max = mid - 1;                      //最大角标值变化
                        }else if (key > arr[mid]) {            //如果传入的值大于了中间角标值
                                min = mid + 1;                             //最小角标值变化
                        }else {                                       
                                return mid;
                        }
                }

                return -1;                                         //没有折半的可能直接返回-1
        }
}

---

作者: EYE_SEE_YOU    时间: 2013-9-21 18:55
既然不是未解决的问题，应该设置其他分类

---

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

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