黑马程序员技术交流社区

标题: 二分查找 [打印本页]

---

作者: 逆袭白富美    时间: 2015-7-10 22:10
标题: 二分查找
public static void main(String[] args)
        {
                int[] arr = {9,12,15,24,36,41,59,68};

                int index = binarySearch(arr,45);
                System.out.println("index="+index);

               
        }
        //二分查找。前提：数组必须是有序的。
        /*
        思路：
        1，通过角标先获取中间角标上元素。
        2，让该元素和要找的数据比较。
        3，如果要找的数大了，缩小范围，要找的范围应该是 中间的角标+1---尾角标。
                如果要找的数小了，要找的范围 头角标---中间角标-1；
        4，不断如此重复，就可以找到元素对应的角标。
        */

        public static int binarySearch(int[] arr,int key)
        {
                //1,定义三个变量，记录头角标，尾角标，中间角标。
                int max,min,mid;
                min = 0;
                max = arr.length-1;
                mid = (max+min)>>1;

                while(arr[mid]!=key)
                {
                        if(key>arr[mid])
                                min = mid + 1;
                        else if(key<arr[mid])
                                max = mid - 1;

                        //判断元素是否存在。
                        if(max<min)
                                return -1;

                        mid = (max+min)>>1;
                }

                return mid;
        }
       
        public static int binarySearch(int[] arr,int key)
        {
                //1,定义三个变量，记录头角标，尾角标，中间角标。
                int max,min,mid;
                min = 0;
                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;
        }






        //查找。
        /*
        需求；查找一个元素在数组中的第一次出现的位置。
        */
        public static int searchKey(int[] arr,int key)
        {
                //遍历查找。
                for(int x=0; x<arr.length; x++)
                {
                        if(arr[x]==key)
                                return x;
                }
                return -1;//-1,代表的是角标不存在的情况。
        }

---

作者: 发抖的_DtYJA    时间: 2015-7-10 22:13
好厉害的样子

---

作者: 曲终烟尽    时间: 2015-7-10 22:18
看到binarySearch好熟悉的感觉，学完忘了，原理记得，然后我找到了Arrays.binarySearch。是一样的。

---

作者: 房东告诉对方    时间: 2015-7-15 16:00
看不懂啊

---

作者: jake_liu    时间: 2015-7-15 17:45
又复习了一遍

---

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

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