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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 王少雷 高级黑马   /  2013-3-6 10:34  /  1809 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 王少雷 于 2013-3-7 08:58 编辑

Arrays.binarySearch(new int[]{1,3,4}, 2); -2
Arrays.binarySearch(new int[]{1,2,3}, 2); 2
Arrays.binarySearch(new int[]{1,2,3}, 1); 0
API中:
返回:
如果它包含在数组中,则返回搜索键的索引;否则返回 (-(插入点) - 1)。插入点 被定义为将键插入数组的那一点:即第一个大于此键的元素索引,如果数组中的所有元素都小于指定的键,则为 a.length。注意,这保证了当且仅当此键被找到时,返回的值将 >= 0。
  依照这个工作,原理,有人能说一下内部算法吗。

评分

参与人数 1技术分 +1 收起 理由
洪建超 + 1

查看全部评分

3 个回复

倒序浏览
public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;//数组下标而不是 数组的值
        int high = toIndex - 1;//数组下标而不是 数组的值

        while (low <= high) {
            int mid = (low + high) >>> 1;//如果我写的话(low+high)/2 学习了 人家写的就是好啊 效率问题
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

评分

参与人数 1黑马币 +9 收起 理由
洪建超 + 9

查看全部评分

回复 使用道具 举报
你可以去看下数据结构。这个上面这些方法很多。

二分法查找的原理就是:
  数据是按升序排列。
  用序列最大和序列最小相加除以2以后用此数与你需要查找的数比较大小。如果大于中间数则到后半段继续之前的操作。直到找到其为止!

评分

参与人数 1黑马币 +6 收起 理由
洪建超 + 6

查看全部评分

回复 使用道具 举报
本帖最后由 张洪慊 于 2013-3-6 15:17 编辑

我以前的总结,关键看两个查找过程
/*        
折半(二分)查找:      
算法思想:
要求序列必须有序(升序/降序),因为只有这样才能确定数据的范围,通过不断的折半来缩小查找数据的范围         
设查找数据为key
①通过两个变量min和max来指定数据的范围,要求min<=max (min=max表示只有一个数据时)         
②首先与mid=(min+max)/2比较,如果key=mid查找成功,直接返回mid,如果key<mid,则min=mid-1,缩短查找范围,此时在让key与mid=(max+min)/2比较,若key>mid,
则max=mid+1,之后再与新的mid比较,依次类推找到则返回,未找到则min>max.
*/
1.找到(图形代表查找过程mid,min,max值的变化)

以上0,1...代表数组下标
2.未找到:




评分

参与人数 2技术分 +1 黑马币 +40 收起 理由
王少雷 + 40 赞一个!
洪建超 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马