黑马程序员技术交流社区

标题: 数组折半查找 [打印本页]
作者: 田向向    时间: 2012-7-1 00:01
标题: 数组折半查找
本帖最后由 田向向 于 2012-7-1 08:25 编辑

不知道是不是今天给别人搬行李把脑子给累出毛病的原因，刚才在看比老师的视频（数组折半查找）中，为什么会取最大值max=arr.length-1;这个视频这一段我连着看了三四遍，都没看明白，请指点，，我是初学者，希望大家不要嘲笑我。

2.jpg (11.46 KB, 下载次数: 43)

2.jpg
作者: 赵志勇    时间: 2012-7-1 00:21
数组的首位是从角标0开始的。所以最后的角标应为length-1.这你应该明白了，不明白可以继续问。

2.jpg (11.46 KB, 下载次数: 44)

2.jpg
作者: 田向向    时间: 2012-7-1 00:29
赵志勇 发表于 2012-7-1 00:21
数组的首位是从角标0开始的。所以最后的角标应为length-1.这你应该明白了，不明白可以继续问。 ...

你的意思是说，数组的那个length是从1开始的，，但是角标是从0开始的，，所以到最后一个应该用length-1，对吗？？
作者: 孙飞    时间: 2012-7-1 00:38
本帖最后由 feigecal 于 2012-7-1 00:39 编辑

折半查找是每次都用中间角标位置上的值mid和要查找 的值比较，如果小于要查找的值那么说明要查找的值在mid的右边，那么就把mid的角标加一的角标上的值做为最小值，再进行折半，如果mid大于要查找的值，那就把mid的角标减一的角标上的值做为最大值再进行折半，只所以max=arr.length-1,是因为arr.length是数组的长度，而数组的角标是从0开始的，所以最大角标就是长度减去1了。给你个例子看看
  1. /**
  2. 用折半法在一个数组中查找指定的值在数组中的角标位
  3. */
  4. class ZheBan
  5. {
  6. public static void main(String[] args)
  7. {
  8. int [] arr={3,4,6,3,7,9,8,2};
  9. int a=chaZhao(arr,7);//调用查找功能
  10. System.out.println(a);
  11. }
  12. public static int chaZhao(int[] arr,int key)//定义一个功能，用于查找
  13. {
  14. int min,mid,max;
  15. min=0;
  16. max=arr.length-1;
  17. while(min<=max)
  18. {
  19. mid=(min+max)/2;
  20. if (key<arr[mid])
  21. {
  22. max=mid-1;
  23. }
  24. else if(key>arr[mid])
  25. {
  26. min=mid+1;
  27. }
  28. else
  29. return mid;
  30. }
  31. return -1;//数组中没有要查找的数时打印出-1
  32. }
  33. }
复制代码
作者: 赵志勇    时间: 2012-7-1 08:03
田向向 发表于 2012-7-1 00:29
你的意思是说，数组的那个length是从1开始的，，但是角标是从0开始的，，所以到最后一个应该用length-1， ...

应该是这样，如果length 是1，则角标是0.
作者: 邵阳    时间: 2012-7-1 08:17
本帖最后由 邵阳 于 2012-7-1 08:36 编辑

楼主我一看到你的问题我都感觉哪里好像不对，然后又看了看视频，对于你给出的数组是不能用于折半查找的。
折半查找不同于一般查找，折半查找前提是数组里面的元素必须是由小往大（或者由大往小）。
所以显然你的数组不符合这种情况，所以你的先将数组先排序，然后用折半查找，否则你要么不能的得出正确结果，要么结果是错误的。
对于你说的max=arr.length-1，因为数组里面每个元素都有一个角标，角标是从0开始分配的，还有arr.length表示数组里面的元素个数，又max代表最大角标值，所以max必然是arr.length-1. 此时mid=0




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