黑马程序员技术交流社区

标题: Collections工具包中关于binarySearch?求指教 [打印本页]

---

作者: 乔九    时间: 2013-2-24 09:47
标题: Collections工具包中关于binarySearch?求指教
package com.itcast;

import java.util.Arrays;

public class StaticImport {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[]arr={3,2,4};
                //Arrays.sort(arr);注释此句后，排序查找3结果为-3，注释前为排序后的位置？？？求解
                System.out.println(Arrays.toString(arr));
                int index=Arrays.binarySearch(arr,3);
                System.out.println(index);

        }

}

---

作者: 罗海云    时间: 2013-2-24 10:17

对了,看到楼下.突然还有发现有个问题没答道...就是折半查找的数组必须是有序的..

1. private static int binarySearch0(short[] a, int fromIndex, int toIndex,
   
2. short key) {
   
3. int low = fromIndex;          <FONT color=red>//下面就让我带着你跟着程序一步一步的走.   这个是我去看的src包中的源码/  low = 0;</FONT>
   
4. int high = toIndex - 1;        // high = arr.length - 1;   high = 2;
   
5. 
   
6. while (low <= high) {        // 0 <= 2    成立向下执行
   
7. int mid = (low + high) >>> 1;    // mid = (0+2)>>>1    mid=1
   
8. short midVal = a[mid];      midVal = a[1]    midVal = 2
   
9. 
   
10. if (midVal < key)       midval < 3;  成立
    
11. low = mid + 1;    //  low = 1+1  low = 2;
    
12. else if (midVal > key)   
    
13. high = mid - 1;
    
14. else
    
15. return mid; // key found
    
16. }
    
17. return -(low + 1); // key not found.<FONT color=red>returnh -(2+1);  就是这样了./..</FONT>

复制代码

呵呵,解释完毕..谢谢

---

作者: 柴乔军    时间: 2013-2-24 10:24
折半查找方法是要建立在有序序列的基础上的，必须先对原数组进行排序才能进行折半查找

---

作者: 胥文    时间: 2013-2-24 14:54
binarySearch（），二分法其实就是折半查找
在使用二分搜索法来搜索指定的 int 型数组，以获得指定的值。必须在进行此调用之前对数组进行排序（通过 sort(int[]) 方法）。如果没有对数组进行排序，则结果是不确定的。如果数组包含多个带有指定值的元素，则无法保证找到的是哪一个
至于你的为什么是-3
如果你要找的值它包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入数组的那一点：即第一个大于此键的元素索引，如果数组中的所有元素都小于指定的键，则为 a.length。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0
而这里通过二分法找到第一个大于3的数是4（而4的索引是2，按照上面的算法就是-3）

---

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

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