黑马程序员技术交流社区

标题: 基础视频中的一个纰漏（halfSort）哈哈找上瘾了 [打印本页]

作者: 贺靖轩 时间: 2013-4-1 11:18
标题: 基础视频中的一个纰漏（halfSort）哈哈找上瘾了
本帖最后由贺靖轩于 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();

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

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

作者: 刘胜寒 时间: 2013-4-1 11:39
老师没告诉你，TreeSet只能保存唯一一个元素的吗？如果有重复的...用折半查找确实不靠谱...不过可以优化一下，按照老师的方法重写一下折半查找的方法
假如你查找2，你折半查找一下1，然后查找3，根据这个两个返回的东西，判断2这个玩意在数组中的起始位置，你不就知道了嘛...对不对

作者: 贺靖轩 时间: 2013-4-1 12:04

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

有道理，问题是
１。我都不知道这数组到底长啥样，咋找到这两个参考数？
２。如果　1　３正好是参考数，但他们也有多个，起始位置就不靠谱了吧？
３．恩这两数找到了确实是1和3 找1的终结位置和找3的起始位置又把问题变得更复杂了。现在找的不只是2 的相关信息了，连1 和 3 也成了思考成本，代价太大。
4.感觉这方法不太可行，我上个厕所。

作者: 贺靖轩 时间: 2013-4-1 17:11
求解啊啊啊啊啊啊啊啊~~~~~~~~~~~~~~~~~~~~~~~

作者: 邵彩华 时间: 2013-4-1 17:37

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

你能确定1和2在数组中就一定也是唯一的吗？

作者: 贺靖轩 时间: 2013-4-1 22:16

邵彩华发表于 2013-4-1 17:37
你能确定1和2在数组中就一定也是唯一的吗？

是啊呵呵所以想求一个比较可行的思路。

作者: 陈丽莉 时间: 2013-4-8 10:32
我觉得对于大多数需要查找的一组数来说，重复的数还是占少数的；

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

当然有想法是好的，也可以自己实现下，只是对于折半这个方法来说，老师讲的并没有问题~

作者: 刘胜寒 时间: 2013-4-8 16:59

陈丽莉发表于 2013-4-8 10:32
我觉得对于大多数需要查找的一组数来说，重复的数还是占少数的；

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

师姐给我几分钟...
我来帮他解决这个问题....
记得给我两分技术分...
我就知足了....哈哈哈

作者: 刘胜寒 时间: 2013-4-8 17:40

public static void main(String[] args)
{
int[] arr=new int[]{1,2,2,2,2,2,2,3,6,6,6};
int index1 = halfSearch(arr,6);
System.out.println(index1);
}
public static int halfSearch(int[] arr,int key)
{
int min,max,mid=0;
min=0;
max=arr.length-1;
if(key<arr[0])return 0;
if(key>arr[max]) return -max-1;
for(int i=0;i<32;i++)
{
mid=(max+min)>>1;
if(key>=arr[mid])
{
min=mid+1;
}
else
{
max=mid-1;
}
}
if(key==arr[mid]) return mid;
return -mid;
}

复制代码

// 折半查找返回key最后一次出现的位置
否则返回负数
存在一个小问题
就是你要查的数比你arr[0]还要小的话返回的是0 你们懂得

作者: 刘胜寒 时间: 2013-4-8 18:40

陈丽莉发表于 2013-4-8 10:32
我觉得对于大多数需要查找的一组数来说，重复的数还是占少数的；

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

师姐....你技术分有点紧....
云三的妹子紧不紧张啊....
^_^

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

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