A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 程序爱好者 中级黑马   /  2014-4-17 09:24  /  1951 人查看  /  10 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 程序爱好者 于 2014-4-17 10:50 编辑
  1. import java.util.*;;

  2. public class Test {
  3.         public static void main(String[] args) {
  4.                 List<String> list=new ArrayList<String>();
  5.                 list.add("abcfdsfdsf");
  6.                 list.add("cdtw");
  7.                 list.add("da");
  8.                 list.add("da");
  9.                 list.add("dd");
  10.                 list.add("zbcfd");
  11.         //        Collections.sort(list);
  12.                 sop(list);
  13.         //        int index=halfSearch(list,"cdtwa");
  14.                 int index=halfSearch(list,"cdtw",new com());
  15.                 sop("index="+index);
  16.         }
  17.         public static int halfSearch(List<String> list,String key,Comparator<String> com)//这方法下面的代码怎么理解?
  18.         {
  19.                 int max,min,mid;
  20.                 max=list.size()-1;
  21.                 min=0;
  22.                 while(min<=max)
  23.                 {
  24.                         mid=(max+min)>>1;
  25.                         String str=list.get(mid);
  26.                         int num=str.compareTo(key);
  27.                         if (num>0) {
  28.                                 max=mid-1;
  29.                         }else if (num<0) {
  30.                                 min=min+1;
  31.                         }else{
  32.                                 return mid;
  33.                         }
  34.                 }
  35.                 return -min-1;
  36.                
  37.         }
  38.         public static void sop(Object obj)
  39.         {
  40.                 System.out.println(obj);
  41.         }
  42.         
  43. }
复制代码


谁能给我详细的说一下那个折半的原理

评分

参与人数 1技术分 +1 收起 理由
黑妞~ + 1

查看全部评分

10 个回复

倒序浏览
看看视频把选择二分法查找,数据必须是有序的,先把字符串存储到Arreylist集合中,对对象进行自然排序。给定的字符串与集合中间的对象比较,大于时,min角标不变,max=mid;小于时,max不变min=mid;依次循环。当max<min时,返回mid.语言表达能力有限,凑合离间吧。取mid值时用到了位运算符
回复 使用道具 举报 1 0
本帖最后由 anqi 于 2014-4-17 09:48 编辑

     折半查找(2分查找)方法的前提是: “已经排序好的线性表”。我们的一维数组就是线性表。一位数组中的成员数据必须已经排序好了,才能用二分法来进行查找操作。排序可以是升序,也可是降序。                                                                                            我们假设有一个20个数据的一维数组,升序。[a1,a2,a3,........,a20] 我们要查找的数据值为Rey 。中间位置的计算方法为:mid=(max+min)/2。首先 Rey与数组的第10个成员进行比较。如果Rey>a10,那么我们要找的数据就可能在数组的第11到20成员之间,反之,Rey<a10,我们要找的数据就可能在数组的1到9之间。这样就确定了定了新的寻找范围。重复以上步骤,直到寻找结束。
    所以这个算法的原理是:min小于max就能折半。(因为min和max之间还存在区间,要找的数就在这区间内,要无限的缩小这个区间确定Rey的位置)
至于计算的时候为什么是mid+1,而不是mid。因为mid=(max+min)/2是自动取整的。防止进入死循环。








回复 使用道具 举报
使用二分查找要求被查找的数组是排好序的。
比如,查找的数组是从小到大排列的。
先计算这个数组的中值(mid=(max+min)>>1),若小于中值,去数组的前半部分查找(max = mid-1),不然后就是后半部分查找(min=mid+1),不断迭代这个过程,直到查到相应值或区间小于等于0。
二分查找感觉像二叉树,每个区间的中值为父节点,最先与父节点(也就是中值比较),然后去左子树,或者右子树,循环以左(右)子树这个节点为父节点,比较后再查找它的左子树或右子树。
回复 使用道具 举报
anqi 发表于 2014-4-17 09:42
折半查找(2分查找)方法的前提是: “已经排序好的线性表”。我们的一维数组就是线性表。一位数组中 ...

看了你说的前面的都懂了,就这句还不是很理解
至于计算的时候为什么是mid+1,而不是mid。因为mid=(max+min)/2是自动取整的。防止进入死循环。
能再给我详细说说这句吗
回复 使用道具 举报
呆呆沙师妹 发表于 2014-4-17 09:45
使用二分查找要求被查找的数组是排好序的。
比如,查找的数组是从小到大排列的。
先计算这个数组的中值(mi ...

max = mid-1      min=mid+1
这两个能给我说详细点嘛  
回复 使用道具 举报
程序爱好者 发表于 2014-4-17 10:10
max = mid-1      min=mid+1
这两个能给我说详细点嘛

假设是有10个元素的数组,那么整个整数的角标范围为0~9。
即第一次查找时,min =0 ,max = 9, mid = 4;若没有查找到,假定比角标为mid的值小;则查找进入左区间,即0~3,因为角标4已经比较了,比它大(若比mid值大,进入右区间,即5~9);
第二次查找时,min = 0,max = 3(max = mid - 1);因为min < max, 循环继续。
这样能明白么?
回复 使用道具 举报
anqi 中级黑马 2014-4-17 10:24:41
8#
本帖最后由 anqi 于 2014-4-17 10:26 编辑
程序爱好者 发表于 2014-4-17 10:08
看了你说的前面的都懂了,就这句还不是很理解
至于计算的时候为什么是mid+1,而不是mid。因为mid=(max+ ...

假设一个顺序的1,2,3,4,5
比如说你计算的值在4,5之间,要是min=mid
第一次循环在3,5,mid=4,
那么第2次循环在4,5之间, mid=(4+5)/2=4 ,自动取整,
无数次循环 min=4 max=5 mid=4,无法结束。
而取min=mid+1,就是为了叫循环能结束
回复 使用道具 举报
1  5  6   7    9   11  
假如这就是集合中的元素  你查找的数是7
min=0   max=list.size()-1(也就是5)
mid 则等于   mid=(0+5)/2=2  
看一下索引2 的位置是  6  你的查找的7会与6进行比较   因为比6大它肯定是在6的右边   所以你的min要将min往6的右边移动  因为6的位置是mid  所以你必须从6右边的那为开始 ,所以肯定是6的位置+1 也就是mid+1

mid-1的情况正好相反,这个你自己推理一下,有助于理解
回复 使用道具 举报
⒈心只霸占沵 发表于 2014-4-17 10:29
1  5  6   7    9   11  
假如这就是集合中的元素  你查找的数是7
min=0   max=list.size()-1(也就是5)

谢谢    理解了
回复 使用道具 举报
anqi 发表于 2014-4-17 10:24
假设一个顺序的1,2,3,4,5
比如说你计算的值在4,5之间,要是min=mid
第一次循环在3,5,mid=4,

谢谢了  听你这么一说我开窍了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马