黑马程序员技术交流社区

标题: 如何让折半查找出多个重复数 [打印本页]
作者: Wqi    时间: 2015-7-19 20:17
标题: 如何让折半查找出多个重复数
本帖最后由 Wqi 于 2015-7-19 20:18 编辑
  1. <div class="blockcode"><blockquote>//折半查找,数组必须有序。
  2.         public static void zBCZ(int[] arr,int key)
  3.         {       
  4.                 selectSort(arr);//先排序，有序后在查找。
  5.                 int num = 0;
  6.                 int min = 0;
  7.                 int max = arr.length-1;
  8.                 int mid = 0;
  9.                 while(min <= max)
  10.                 {
  11.                         mid = (min+max)/2;
  12.                         if(arr[mid] == key)
  13.                         {       
  14.                                
  15.                                 num = mid +1;
  16.                                 System.out.println(key+"位于数组中从小到大排序后的第"+num+"号位置!");
  17.                                 max = max -2;
  18.                                 continue;
  19.                         }
  20.                         else if(arr[mid] >key)
  21.                         {
  22.                                 max = mid-1;
  23.                                
  24.                         }
  25.                         else
  26.                         {       
  27.                                 min = mid +1;
  28.                                
  29.                         }
  30.                 }
  31.                 if(num == 0)
  32.                         System.out.println("数组中没有"+key+"这个数！");
  33.         }
  34.                
复制代码




5H_{FN0~]H60E484K(~L_KT.png (5.58 KB, 下载次数: 14)

重复提示

重复提示
作者: Wqi    时间: 2015-7-19 20:19
请问如何修改能去掉重复的提示。。
作者: Wqi    时间: 2015-7-19 20:21
if(arr[mid] == key)
{       
num = mid +1;
System.out.println(key+"位于数组中从小到大排序后的第"+num+"号位置!");
max = max -2;
continue;     
｝
这部分需要如何修改？求各位指导。。。
作者: Wqi    时间: 2015-7-19 20:23
。。。。我想清楚了。。应该查找到后，再向左和向右分别查找重复，不能在折半了。。。

作者: Wqi    时间: 2015-7-19 20:49
晕。还是无法判断向左向右各查找多少次，总不能遍历吧。。。求指导如何实现用折半查找出重复数。
渣渣搞不定啊，大神们快来。。。
作者: 为明天而奋斗    时间: 2015-7-19 21:16
利用折半查找找到第一个值后，min=mid-1，max=mid+1，然后再利用循环让要查找的key与前后进行比较
作者: 陈建民1    时间: 2015-7-19 21:31
找到第一个符合的mid后，再找前一个和后一个位置，以此类推。因为数组是排序后的，如果有多个存在，肯定是在mid的相邻位置。
作者: Wqi    时间: 2015-7-19 21:47
谢谢以上各位。已经搞定了。
  1. public static void zBCZ(int[] arr,int key)
  2.         {
  3.                 int e = arr.length-1;
  4.                 int s = 0;
  5.                 search(arr,key,s,e);
  6.         }
  7.         private static void search(int[] arr,int key,int s,int e)
  8.         {
  9.                 int count = 0;
  10.                 if(s>e)
  11.                         return;
  12.                 int mid = (s+e)/2;
  13.                 if(arr[mid]>key)
  14.                         search(arr,key,s,mid-1);
  15.                 else if(arr[mid]<key)
  16.                         search(arr,key,mid+1,e);
  17.                 else
  18.                 {
  19.                         search(arr,key,s,mid-1);
  20.                         count = mid+1;
  21.                         System.out.println(key+"的位置是"+count);
  22.                         search(arr,key,mid+1,e);
  23.                 }
  24.                        
  25.                
  26.         }
复制代码







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