黑马程序员技术交流社区

标题: 数组中的折半两种折半查找法 [打印本页]

---

作者: 追逐    时间: 2014-3-6 20:05
标题: 数组中的折半两种折半查找法
/*
折半查找，查找数组中的某个数是否存在于数组中，存在的话会存在在那个位置
*/
class ZheBanTest {
       
        //定义一个函数，查找未知数是否存在于数组中，存在的话会在什么位置
        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]) //如果这个数大于中间数，最小值就为中间数加1
                                min = mid + 1;
                        else if(key < arr[mid])
                                max = mid - 1;
                        if(min > max) //假如最小值大于最大值了。就不在运行下去了，返回-1；
                                return -1;
                        mid = (max + min) / 2; //每次循环中间数必须做的运算，让中间数随时改变
                }
                return mid; //如果等于中间数就说明找到了。把找到的位置返回出去
        }
       
        //折半查找的第二种方法
        public static int halfSearch_1(int[] arr, int key) {
                //定义最大、最小和中间值
                int min = 0, max = arr.length - 1, mid;
                //定义循环查找
                while(min <= max) {
                        mid = (min + max) / 2;
                        if(key > arr[mid]) {
                                min = mid + 1;
                        } else if(key < arr[mid]) {
                                max = mid - 1;
                        } else
                                return mid;
                }
                return -1;
        }
       
        public static void main(String[] args) {
                int[] arr = {2,4,6,7,9,12,14};
                int index = halfSearch_1(arr, 9);
                System.out.print(index);
        }
       
}

---

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

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