黑马程序员技术交流社区

标题: 二分（折半）查找的详细解说 [打印本页]
作者: coqns    时间: 2012-12-11 15:30
标题: 二分（折半）查找的详细解说
本帖最后由 coqns 于 2012-12-11 15:33 编辑

在上周就见了一位同学在论坛上贴出了他自己写的二分查找的代码（有错，代码有一个语句没放进循环里）来问人解决，今天在论坛上又看见有人问binarySearch （二分查找），于是我把自己当初学二分查找时写的代码贴出来了，注释写的很详细，而且是绝对可以跑通的~
  1. class BinarySearch
  2. {
  3.      public static void main(String[] args)
  4.      {
  5.          //定义数组
  6.          int[] arr={-4,-2,0,2,4,6};
  7.          //得到要找的元素在数组中的角标
  8.          int r=result(arr,6);
  9.          System.out.println("结果是："+r);
  10.      }
  11.      
  12.      //二分法，也称折半查找，效率比较高。
  13.      public static int result(int[] arr,int input)
  14.      {
  15.          int min=0;                //定义最小的角标
  16.          int max=arr.length-1;     //定义最大的角标
  17.          int mid;                  //定义中间的角标

  19.          while (min<=max)
  20.          {
  21.              /*
  22.              每次循环都要给中间角标赋新值（在没有找到要找的元素前，每循环一次，
  23.              最大角标或者最小角标其中必然有一个会变化，相应的中间角标也要变）
  24.              */
  25.              mid=(min+max)/2;
  26.             
  27.              //如果中间角标的值小于要找的数（也就是说要找的数在数组右边）
  28.              if (arr[mid]<input)
  29.                  //就把最小角标变为原中间角标+1（相当于把左边去掉）
  30.                  min=mid+1;
  31.              //如果中间角标的值大于要找的数（也就是说要找的数在数组左边）
  32.              else if (arr[mid]>input)
  33.                  //把最大角标变为原中间角标-1（相当于把右边去掉）
  34.                  max=mid-1;
  35.              else
  36.                  //如果中间角标的值等于要找的数。。。就说明找到了，直接返回要找的值对应的角标
  37.                  return mid;

  39.          }
  40.          //循环后如果还没有找到，返回-1
  41.          return -1;
  42.      }
  43. }
复制代码
作者: 卞潇洋    时间: 2012-12-11 22:03
本帖最后由 天堂木乃伊 于 2012-12-11 22:06 编辑

受用了，谢谢！在此贴出根据你的二分法写出的俺滴二分查找法，嘿嘿~希望莫吐嘈：
全部代码就不写出来了，只贴出二分法用的方法吧
  1. public int recFind(long searchKey, int lowerBound,
  2.                                          int upperBound)
  3.       {
  4.       int curIn;

  6.       curIn = (lowerBound + upperBound ) / 2;
  7.       if(a[curIn]==searchKey)
  8.          return curIn;              // 找到要查找的数字
  9.       else if(lowerBound > upperBound)
  10.          return nElems;             // 如果下界大于上界，说明没有找到
  11.       else                          // 如果上界小于下界说明没有找完，继续找，但下面用到递归，更方便一些
  12.          {
  13.          if(a[curIn] < searchKey)   // it's in upper half
  14.             return recFind(searchKey, curIn+1, upperBound);//递归
  15.          else                       // it's in lower half
  16.             return recFind(searchKey, lowerBound, curIn-1);//递归
  17.          }  // end else divide range
  18.       }
复制代码
感觉这个要方便一些，这个用的递归，比循环好一些

作者: coqns    时间: 2012-12-11 22:59
天堂木乃伊 发表于 2012-12-11 22:03
受用了，谢谢！在此贴出根据你的二分法写出的俺滴二分查找法，嘿嘿~希望莫吐嘈：
全部代码就不写出来了，只 ...

写的挺好的，共同进步~



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