黑马程序员技术交流社区

标题: 数组折半查找 [打印本页]

---

作者: 史世锋    时间: 2015-9-13 19:31
标题: 数组折半查找
package com.itheima;

public class Test018
{

        /**
         * 查找一个元素在数组中出现的位置
         * 普通查找：遍历数组，将要查找的值与数组的每个元素进行比较。
         * 折半查找：首先数组是有序的(升序)。MIN = 0, MAX = arr.length -1, MID = (MIN + MID)/2;
         *        先将数组的中间位置元素比较(key == arr[MID])
         *        如果key>arr[MID],MIN = MID+1
         *        如果key<arr[MID],MAX = MID-1;
         *        再将数组的中间位置元素比较(key == arr[MID])
         *        如果找到 该元素的下角标是MID，如果MIN>MAZ还没找到，则key不在数组中
         *        
         * @param args
         */
        public static void main(String[] args)
        {
                int[] arr = new int[]{52, 68, 45, 0, 12, 58, 71, 35, 95, 46};
                Test017.printArr(arr);
               
                int key = 69;
                int index = getIndex(arr, key);
                System.out.println(key +"的位置是：" + index);
               
                //对数组进行排序
                Test017.setAscending_2(arr);
                Test017.printArr(arr);
               
                index = halfSearch(arr, key);
                System.out.println(key +"的位置是：" + index);
        }
        //获取元素出现的位置，如果有，返回下角标，如果没有，返回-1
        public static int getIndex(int[] arr, int key)
        {
                for(int i = 0; i < arr.length; i++)
                {
                        if(arr[i] == key)
                                return i;
                }
                return -1;
        }
        //折半查找(如果找到，返回元素的下角标，如果找不到返回一个位置，使key插入到数组中，数组仍是有序的)
        public static int halfSearch(int[] arr, int key)
        {
                int max = arr.length -1, min = 0, mid = 0;
                for(int i = 0; min <= max; i++)
                {
                        mid = (max + min)/2;
                        if(key > arr[mid])
                        {
                                min = mid + 1;
                        }
                        else if(key < arr[mid])
                        {
                                max = mid - 1;
                        }
                        else
                                return mid; //返回元素的下角标
                }
                return min; //返回插入的位置
        }
}

---

作者: yonghong_cui    时间: 2015-9-13 21:19
看过了 ，受教

---

作者: Wqi    时间: 2015-9-13 21:37
原码插入是-min-1...你可以随便记着

---

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

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