黑马程序员技术交流社区

标题: binarySearch（） 原理怎么理解 [打印本页]

---

作者: 程序爱好者    时间: 2014-4-17 09:24
标题: binarySearch（） 原理怎么理解

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

复制代码

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

---

作者: 邵景伦    时间: 2014-4-17 09:40
看看视频把选择二分法查找，数据必须是有序的，先把字符串存储到Arreylist集合中，对对象进行自然排序。给定的字符串与集合中间的对象比较，大于时，min角标不变，max=mid;小于时，max不变min=mid;依次循环。当max<min时，返回mid.语言表达能力有限，凑合离间吧。取mid值时用到了位运算符

---

作者: anqi    时间: 2014-4-17 09:42


     折半查找（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是自动取整的。防止进入死循环。

---

作者: 呆呆沙师妹    时间: 2014-4-17 09:45
使用二分查找要求被查找的数组是排好序的。
比如，查找的数组是从小到大排列的。
先计算这个数组的中值（mid=(max+min)>>1），若小于中值，去数组的前半部分查找（max = mid-1），不然后就是后半部分查找（min=mid+1），不断迭代这个过程，直到查到相应值或区间小于等于0。
二分查找感觉像二叉树，每个区间的中值为父节点，最先与父节点(也就是中值比较)，然后去左子树，或者右子树，循环以左(右)子树这个节点为父节点，比较后再查找它的左子树或右子树。

---

作者: 程序爱好者    时间: 2014-4-17 10:08

anqi 发表于 2014-4-17 09:42
折半查找（2分查找）方法的前提是： “已经排序好的线性表”。我们的一维数组就是线性表。一位数组中 ...

看了你说的前面的都懂了，就这句还不是很理解
至于计算的时候为什么是mid+1，而不是mid。因为mid＝（max+min）/2是自动取整的。防止进入死循环。
能再给我详细说说这句吗

---

作者: 程序爱好者    时间: 2014-4-17 10:10

呆呆沙师妹 发表于 2014-4-17 09:45
使用二分查找要求被查找的数组是排好序的。
比如，查找的数组是从小到大排列的。
先计算这个数组的中值（mi ...

max = mid-1      min=mid+1
这两个能给我说详细点嘛  

---

作者: 呆呆沙师妹    时间: 2014-4-17 10:20

程序爱好者 发表于 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

程序爱好者 发表于 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，就是为了叫循环能结束

---

作者: ⒈心只霸占沵    时间: 2014-4-17 10:29
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:48

⒈心只霸占沵 发表于 2014-4-17 10:29
1  5  6   7    9   11  
假如这就是集合中的元素  你查找的数是7
min=0   max=list.size()-1（也就是5）

谢谢    理解了

---

作者: 程序爱好者    时间: 2014-4-17 10:49

anqi 发表于 2014-4-17 10:24
假设一个顺序的1，2,3,4,5
比如说你计算的值在4,5之间，要是min=mid
第一次循环在3，5，mid=4，

谢谢了  听你这么一说我开窍了

---

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

黑马程序员IT技术论坛 X3.2