黑马程序员技术交流社区

标题: [已解决]折半查找的问题 [打印本页]
作者: 杨卫腾    时间: 2012-9-2 14:27
标题: [已解决]折半查找的问题
本帖最后由 杨卫腾 于 2012-9-2 17:18 编辑
  1. class ArrayDemo6
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr = {23,99,45,32,76,87,98,86};
  6.                
  7.                 System.out.println("index="+halfSearch(arr,99));
  8.                 System.out.println("index1="+binarySearch(arr,99));
  9.         }

  11.         /*
  12.         *方法：遍历查找
  13.         *参数：整型数组；
  14.         *参数：key,要查找的值
  15.         *返回值：角标
  16.         */
  17.         public static int ergodicSeek(int[] arr, int key)
  18.         {
  19.                 for(int x=0; x<arr.length; x++)
  20.                 {
  21.                         if(arr[x]==key)
  22.                                 return x;
  23.                 }
  24.                 return -1;
  25.         }

  27.         /*
  28.         *方法：折半查找
  29.         *参数：整型数组
  30.         *参数：key，要查找的值
  31.         *返回值：角标
  32.         */
  33.         public static int halfSearch(int[] arr,int key)
  34.         {
  35.                 int max,min,mid;
  36.                 max = arr.length-1;
  37.                 min = 0;
  38.                 mid = (max + min)>>1;
  39.                 while(arr[mid]!=key)
  40.                 {
  41.                         if(key>arr[mid])
  42.                                 min = mid+1;
  43.                         else if(key<arr[mid])
  44.                                 max = mid-1;
  45.                         if(max<min)
  46.                                 return -min-1;
  47.                         mid = (max + min)>>1;
  48.                 }
  49.                 return mid;
  50.         }
  51.         /*
  52.         *方法：折半查找
  53.         *参数：整型数组
  54.         *参数：key,要查找的值
  55.         */
  56.         public static int binarySearch(int[] arr,int key)
  57.         {
  58.                 int max,min,mid;
  59.                 max = arr.length-1;
  60.                 min = 0;
  61.                 while(min<=max)
  62.                 {
  63.                         mid = (max + min)>>1;
  64.                         if(key>arr[mid])
  65.                                 min = mid+1;
  66.                         else if(key<arr[mid])
  67.                                 max = mid-1;
  68.                         else
  69.                                 return mid;
  70.                 }
  71.                 return -min-1;
  72.         }
  73. }
复制代码
普通的遍历查找能找到key值，可是折半(二分法)查找虽然效率高，但是却找不到指定的key值，能不能再优化呢？
作者: 袁艳超    时间: 2012-9-2 14:40
折半查找的前提,数组必须是有序的,先对数组排序
作者: 高正新    时间: 2012-9-2 14:42
同学，折半查找，首先要求就是数组是有序的。
作者: 杨卫腾    时间: 2012-9-2 14:47
水木桶 发表于 2012-9-2 14:42
同学，折半查找，首先要求就是数组是有序的。

API 中的Arrays.binarySearch(int[] arr, int key)  方法中也没有设计排序呀，这是为什么？
作者: 杨卫腾    时间: 2012-9-2 14:51
明白了，这个数组在传进去之前就要是有序的！
作者: 董志超    时间: 2012-9-2 16:03
折半查找，前提是数组是有序的。按你的程序要求数组是递增的。
作者: 李志群    时间: 2012-9-2 16:04
二分（折半查找法）：

        角标是有序的，直接获取中间角标上的元素座位判断的依据。
        中间角标 = （头角标+尾角标）/2；（0+5）/2=2;
        数组[中间角标]=25；
        if（key>中间元素）
                头角标= 中间角标+1；
        else if(key<中间元素)
                尾角标=中间角标-1；

        在缩小范围的数组中继续取中间值。
                中间角标 = （头角标+尾角标）/2；（3+5）/2=4;
                数组[中间角标]=57；

在折半的过程总 头角标不断的增大 尾角标不断的在减小。

if（头角标>尾角表）
        return - 1;


演示：二分查找法
：前提：只能对有序的数组进行查找。
public static int binarySearch(int[] arr,int key)
{
//1，需要定义三个变量，用于记录住角标的变化。
        int min,max,mid;
        min = 0;
        max=arr.length-1;
        //只要min和max之间有距离，就有了折半的可能折半多次，使用while循环。

        while(min<max)
                //获取中间角标
                mid =(max+min)/2;//mid =(max=min)>>1;
                //获取中间角标上的元素和key进行比较，
                //来确定min和max的新值，或者叫做。不去确定新的查找范围
                if（key>arr[min]）
                min=mid+1;
                else if(key>arr[mid]
                        max=mid-1;
                else
                        return mid;
               
                )
                return -1;
}
作者: 李志群    时间: 2012-9-2 16:06
给楼主看个小例子：希望可以帮到您 这里面的方法呵呵。
/*
        思考题：
                有一个有序的数组，要求如果往这个数组中添加一个元素，还能继续保证这个数组有序，
                那么这个元素的位置如何获取？

        思路:
        1,既然是有序的数组，还要获取位置。这就是在查找。而且有序就可以使用二分查找。
        2,如果要插入的元素在数组中已存在，只要找这个元素的位置就是要插入的位置。
        3,如果要插入的元素在数组中不存在。
        */

/*

        //二分查找法的另一种写法。
        public static int binarySearch_2(int[] arr,int key)
        {
                int min,max,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(min>max)
                                return -1;
                        mid = (max+min)>>1;
                }

                return mid;

        }



*/
class ErFen1
{
        public static void main(String[] args)
        {
                int[] arr={2,3,5,7,44,55,67,88};
                        int zhao1=zhao(arr,67);
                                System.out.println("zhao1="+zhao1);
        }
        public static int zhao(int[] arr,int key)
        {
                //1，需要定义三个变量,用于记录住角标的变化。
                int min,max,mid;
                        min=0;
                        max=arr.length-1;
                        //只要min和max之间有距离，就有了折半的可能，而且有可能折半多次，使用while循环。。
                        while(min<=max)
                        {
                                        //获取中间角标。
                                        mid=(max+min)/2;
                                       
                        //获取中间角标上的元素和key进行比较。
                        //来确定min和max的新值。或者叫做，确定新的查找范围。
                                        if(key>arr[mid])
                                                min=mid+1;
                                        else if(key<arr[mid])
                                                max=mid-1;
                                        else
                                                return mid;
                       
                        }
                        return min;
               
       
        }


}
作者: 吴通    时间: 2012-9-2 17:15
当数组元素无序的时候，可以采用数组遍历比较的方式查找；
       当数组元素是按一定顺序排列的时候，我们可以采用折半查找方法。
class  ChaZhao
{
       public static void main(String[] args)
       {
              //int[] arr={3,1,5,4,7,9};
              //int Index=getIndex(arr,2);
              //System.out.println("Index="+Index); //如果数组里面有两个要找的数，则为第一个。
              int[] arr={1,2,3,4,5,6,7};
              int Index=halfSearch(arr,6);
              System.out.println("Index="+Index);
       }
       //数组查找
public static int getIndex(int[] arr,int key)
{
       for(int x=0;x<arr.length;x++)
              {
                     if(arr[x]==key)
                            return x;  //这个return执行过后下面的return就不再执行
              }
              return -1; //数组角标都是从0开始的，当没有找到时，角标为-1即为没有找到该值。
}
//折半查找
public static int halfSearch(int[] arr,int key)
{
              int min,max,mid;
              min=0;
              max=arr.length-1;
              mid=(max+min)/2;
              while(arr[mid]!=key)
              {
                     if (key>arr[mid])
                            min=mid+1;
                     else if(key<arr[mid])
                            max=mid-1;
                     if(min>max)
                            return -1;
                     mid=(max+min)/2;
              }
                     return mid;
}
}
作者: 赵家阳    时间: 2012-9-2 17:56
折半查找，首先要求数组是有序的，否则就要实现排序，然后才能折半查找，要不就用遍历查找！



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