黑马程序员技术交流社区

标题: 关于数组的折半查找 [打印本页]
作者: 杜天伟    时间: 2013-7-9 13:25
标题: 关于数组的折半查找
本帖最后由 杨兴庭 于 2013-7-10 22:28 编辑

一个有序数组,如果其中有重复的数，那么要查找这个数的位置的话，用一般查找的方法可以查找到这个数第一次出现的角标,那么如果使用折半查找呢？找出来的角标是哪个呢？还是第一次出现的角标吗？
作者: ＂O_忆_O    时间: 2013-7-9 13:44
也是可以查到第一个出现的角标的啊while(start<end)
     {
         pos=(start+end)/2;
         if(a[pos]==num)  end=pos;//这里检测到要查的数字之后，不停止循环。
         else if(a[pos]<num) start=pos+1;
         else end=pos-1;
     }
if(a[start]==num) return start;//知道折半的开始位为要查的数字时才返回。


作者: 李仕勇    时间: 2013-7-9 14:23
使用折半查找的话，有可能是第一个，也有可能是第二个或者其他的。主要是看你的重复的数的角标位置。
作者: 以防万一    时间: 2013-7-9 14:24
  1. public class Index
  2. {

  4. public static int halfSearch(int b [],int key)
  5. {
  6. int max=b.length-1,min=0,mid;
  7. while(min<=max)
  8. {
  9. mid=(max+min)>>1;
  10. if(key>b[mid])
  11. {
  12. mid=mid+1;
  13. }
  14. else if(key<b[mid])
  15. {
  16. min=mid-1;
  17. }
  18. else
  19. {
  20. return mid;
  21. }

  23. }
  24. return -1;
  25. }


  28. public static void main(String[] args)
  29. {

  31. int [] arr =new int[]{2,5,6,5,9,1};
  32. int index=halfSearch(arr,5);
  33. System.out.println("index="+index);
  34. }

  36. }
复制代码
我的
结果是：index=3，，，是第二个数的角标


作者: 杜天伟    时间: 2013-7-9 14:44
＂O_忆_O 发表于 2013-7-9 13:44  也是可以查到第一个出现的角标的啊while(start

这个代码有点难懂啊
作者: 崔龙飞    时间: 2013-7-9 20:54
楼上的不是有序数组，如果是有序数组折半查找也是元素一次出现的角标位置；
  1. public class Demo1 {
  2.         public static void main(String[] args) {
  3.                 int[] arr = {1,2,4,5,6,6,8,9};
  4.                 System.out.println("index= " + halfSearch(arr,6));
  5.         }

  7.         public static int halfSearch(int[] arr,int num) {       
  8.                 int min = 0,max = arr.length-1,mid = (max+min)/2;                                               
  9.                 while(arr[mid] != num) {                                                                                                               
  10.                         if(num > arr[mid]) {                                       
  11.                                 min = mid+1;                                                       
  12.                         }else if(num < arr[mid]) {                                       
  13.                                 max = mid-1;
  14.                         }
  15.                         if(min > max)                                                               
  16.                                 return -1;
  17.                         else
  18.                                 mid = (max+min)/2;                                               
  19.                 }
  20.                 return mid;
  21.         }
  22. }
复制代码
作者: 杜天伟    时间: 2013-7-9 21:27
崔龙飞 发表于 2013-7-9 20:54  楼上的不是有序数组，如果是有序数组折半查找也是元素一次出现的角标位置； ...

你这个出来是第二个位置呀。
作者: 崔龙飞    时间: 2013-7-10 00:19
杜天伟 发表于 2013-7-9 21:27
你这个出来是第二个位置呀。

汗，是的额。我运行的时候理解成第mid个元素了，重新运行了不同的数，都是第二个数的角标，你是遇到这方面的题了吗？
作者: 杜天伟    时间: 2013-7-10 09:30
崔龙飞 发表于 2013-7-10 00:19  汗，是的额。我运行的时候理解成第mid个元素了，重新运行了不同的数，都是第二个数的角标，你是遇到这方 ...

不是，我是看到这块的时候突然想到的这个问题。有点好奇如果有相同数，找出来会是第几个



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