A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 贺靖轩 于 2013-4-1 11:23 编辑

黑马程序员_毕向东_Java基础视频教程第04天-07-数组(折半查找).avi  
毕老爷这节视频给大家讲了折半查找 提到了折半查找的二种实现方式
还进到使用此方式的前提:有序
但是忽略了另一个方面:无重

代码:
public class SearchTest
{
    public static void main(String[] args)
    {
        int[] arr=new int[]{1,2,2,2,2,2,3};
        int index=getIndex(arr,2);
        System.out.println(index);
    }
    public static int halfSearch(int[] arr,int key)
    {
        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(max+min)>>1;
        while(key!=arr[mid])
        {
            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;
    }
    public static int halfSearch_2(int[] arr,int key)
    {
        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(max+min)>>1;
        while(min<=max)
        {
            mid=(max+min)>>1;
            if(key>arr[mid])
            {
                min=mid+1;
            }
            else if(key<arr[mid])
            {
                max=mid-1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
    public static int getIndex(int[] arr,int key)
    {
        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(max+min)>>1;
        while(min<=max)
        {
            mid=(max+min)>>1;
            if(key>arr[mid])
            {
                min=mid+1;
            }
            else if(key<arr[mid])
            {
                max=mid-1;
            }
            else
            {
                return mid;
            }
        }
        return min;
    }
}
结果:
2 //为查找元素的下标

如果数组中有重复元素,虽然找到了该元素的下标(位于中间的元素) 但却忽略了数组中该元素的个数。
如果数组中只有一个重复元素:

一个省事的方法就是:
借助 TreeSet 可以计算出该元素的个数 至于其位置 可以通过相应推理获得。



Set<Integer> set=new TreeSet<Integer>();
for(int i:arr)
{
    set.add(i);
}
System.Out.Println(set.size());
int numOfKey=set.size()-arr.size();

如果存在多个元素,恩,重复的,大家想办法吧。


我脸皮厚,说我抠的随便喷,哈哈。


评分

参与人数 1技术分 +1 收起 理由
陈丽莉 + 1

查看全部评分

9 个回复

倒序浏览
老师没告诉你,TreeSet只能保存唯一一个元素的吗?如果有重复的...用折半查找确实不靠谱...不过可以优化一下,按照老师的方法重写一下折半查找的方法
假如你查找2,你折半查找一下1,然后查找3,根据这个两个返回的东西,判断2这个玩意在数组中的起始位置,你不就知道了嘛...对不对

评分

参与人数 2技术分 +1 黑马币 +2 收起 理由
陈丽莉 + 1
贺靖轩 + 2

查看全部评分

回复 使用道具 举报
似水像火 发表于 2013-4-1 11:39
老师没告诉你,TreeSet只能保存唯一一个元素的吗?如果有重复的...用折半查找确实不靠谱...不过可以优化一 ...

有道理,问题是
1。我都不知道这数组到底长啥样,咋找到这两个参考数?
2。如果 1 3正好是参考数,但他们也有多个,起始位置就不靠谱了吧?
3.恩 这两数找到了 确实是1和3 找1的终结位置 和找3的起始位置又把问题变得更复杂了。现在找的不只是2 的相关信息了,连1 和 3 也成了思考成本,代价太大。
4.感觉这方法不太可行,我上个厕所。
回复 使用道具 举报
求解啊啊啊啊啊啊啊啊~~~~~~~~~~~~~~~~~~~~~~~
回复 使用道具 举报
似水像火 发表于 2013-4-1 11:39
老师没告诉你,TreeSet只能保存唯一一个元素的吗?如果有重复的...用折半查找确实不靠谱...不过可以优化一 ...

你能确定1和2在数组中就一定也是唯一的吗?
回复 使用道具 举报
邵彩华 发表于 2013-4-1 17:37
你能确定1和2在数组中就一定也是唯一的吗?

是啊 呵呵 所以想求一个比较可行的思路。
回复 使用道具 举报
我觉得对于大多数需要查找的一组数来说,重复的数还是占少数的;

而且若是先将重复的去除再进行查找,多半反而会更浪费时间;

当然有想法是好的,也可以自己实现下,只是对于折半这个方法来说,老师讲的并没有问题~
回复 使用道具 举报
陈丽莉 发表于 2013-4-8 10:32
我觉得对于大多数需要查找的一组数来说,重复的数还是占少数的;

而且若是先将重复的去除再进行查找,多半 ...

师姐给我几分钟...
我来帮他解决这个问题....
记得给我两分技术分...
我就知足了....哈哈哈
回复 使用道具 举报
  1. public static void main(String[] args)
  2.     {
  3.              int[] arr=new int[]{1,2,2,2,2,2,2,3,6,6,6};
  4.          int index1 = halfSearch(arr,6);     
  5.          System.out.println(index1);
  6.     }

  7.     public static int halfSearch(int[] arr,int key)
  8.     {
  9.         int min,max,mid=0;
  10.         min=0;
  11.         max=arr.length-1;
  12.         if(key<arr[0])return 0;
  13.         if(key>arr[max]) return -max-1;
  14.         for(int i=0;i<32;i++)
  15.         {       
  16.                 mid=(max+min)>>1;
  17.             if(key>=arr[mid])
  18.             {
  19.                 min=mid+1;
  20.             }
  21.             else
  22.             {
  23.                 max=mid-1;
  24.             }
  25.         }
  26.         if(key==arr[mid]) return mid;
  27.         return -mid;
  28.     }
复制代码
// 折半查找返回key最后一次出现的位置
否则返回负数
存在一个小问题  
就是 你要查的数比你arr[0]还要小的话返回的是0 你们懂得

评分

参与人数 1技术分 +1 收起 理由
陈丽莉 + 1 最近手里有点紧,就给你一分吧~ O(∩_∩)O~.

查看全部评分

回复 使用道具 举报
陈丽莉 发表于 2013-4-8 10:32
我觉得对于大多数需要查找的一组数来说,重复的数还是占少数的;

而且若是先将重复的去除再进行查找,多半 ...

师姐....你技术分有点紧....
云三的妹子紧不紧张啊....
^_^
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马