黑马程序员技术交流社区

标题: 折半查找法 [打印本页]
作者: mishisanyi    时间: 2015-6-17 16:21
标题: 折半查找法
  1. /**
  2. *
  3. */
  4. package array;

  6. /**
  7. * @author mishi
  8. *
  9. */
  10. public class Bisearch {

  12.         /**
  13.          * @param args
  14.          */
  15.         public static void main(String[] args) {
  16.                 // TODO 自动生成的方法存根
  17.                 int[] array = {1,3,5,7,9,11,14,15,16,17,20};
  18.                 System.out.println(bisearch(array,0,array.length,20));
  19.         }
  20.         public static int bisearch(int array[],int fromIndex,int endIndex,int num)
  21.         {
  22.                 int half = (fromIndex + endIndex)/2;
  23.                 while(half!=fromIndex&&half!=endIndex)
  24.                 {
  25.                         if(num<array[half])
  26.                         {
  27.                                 return bisearch(array, fromIndex, half, num);
  28.                         }
  29.                         else if(num>array[half]) {
  30.                                 return bisearch(array, half+1, endIndex, num);
  31.                         }
  32.                         else
  33.                                 return half;
  34.                 }
  35.                 if(num == array[half])
  36.                         return half;
  37.                 return -1;
  38.         }

  40. }
复制代码
作者: Nemo    时间: 2015-6-17 16:56
不错不错哦。学习中。。。
作者: lucien_he    时间: 2015-6-17 18:11
留一下  学学
作者: qq2403956244    时间: 2015-6-17 19:05
本帖最后由 qq2403956244 于 2015-6-17 19:33 编辑

  1. /**
  2. 折半查找 --->英文单词：bisearch
  3. @author q...4
  4. */
  5. /*
  6. 1.需求：改进楼主代码

  8. 2.思路：发现，楼主代码中有如下问题
  9. a.while循环，每执行一次循环都要调用一次本身，假如数很多效率低。
  10. b.循环条件需稍作修改。
  11. c.当 num >20时，比如 num=23 ,这时就会报错ArrayIndexOutOfBoundsException。

  13. 3.步骤：a.用一个while循环就可以完成查找。
  14. b.循环条件只需 头角标(索引) <= 尾角标。
  15. c.尾角标 = 数组.长度 - 1。
  16. */
  17. public class Bisearch
  18. {

  20. /**
  21. * @param args
  22. */
  23. //主函数
  24.     public static void main(String[] args)
  25.     {
  26.              // TODO 自动生成的方法存根
  27.       int[] array = {1,3,5,7,9,11,14,15,16,17,20};
  28.                   // 0 1 2 3 4 5 6 7 8 9 10 角标
  29.       System.out.println("Index="+bisearch(array,0,array.length-1,20));
  30.     }

  32.    //定义一个方法判断需要查找的元素是否在数组中，是->直接返回结果，不是->返回-1 。(角标没有负数)
  33.     public static int bisearch(int array[],int fromIndex,int endIndex,int num)
  34.     {

  36.         while(fromIndex <= endIndex)    //half!=fromIndex&&half!=endIndex
  37.         {
  38.            int half = (fromIndex + endIndex)/2;   //中角标。5,8,9,10

  40.         if(num<array[half])     //20<11,20<16,20<17,20<20
  41.        {
  42.            endIndex = half-1;    //return bisearch(array, fromIndex, half, num);

  44.        }
  45.        else if(num>array[half]) {    //20>11,20>16,20>17

  47.           //return bisearch(array, half+1, endIndex, num);
  48.             fromIndex = half+1;      //6,9,10
  49.        }
  50.       else
  51.        {
  52.               return half;   //10
  53.        }
  54.     }
  55.       //if(num == array[half])
  56.        // return half;
  57.        return -1;
  58.     }
  59. }
复制代码



作者: zc强盗    时间: 2015-6-17 21:07
学了就忘了
作者: mishisanyi    时间: 2015-6-18 14:37
谢谢大家的支持，楼上的我都加了黑马分，谢谢啦
作者: yzzojf    时间: 2015-6-18 14:58
留存，学习，辛苦了！



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