当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

Arrays.binarySearch()

发表于: 2013-05-26   作者:aty   来源:转载   浏览次数:
摘要:       最近做1个OJ题目,其中有一步这样的操作:给定一个排序好的数组,随意给定一个数据,寻找数组中第一个大于或等于该值的数据在数组中的索引。如{1,4,5,10}, 给定4,应该返回的索引是1;给定6应该返回的索引是3        刚开始我用的是直接从前到后扫描一遍这种最原始的方法,跑junit用例的时候,发现此处存

      最近做1个OJ题目,其中有一步这样的操作:给定一个排序好的数组,随意给定一个数据,寻找数组中第一个大于或等于该值的数据在数组中的索引。如{1,4,5,10}, 给定4,应该返回的索引是1;给定6应该返回的索引是3

 

     刚开始我用的是直接从前到后扫描一遍这种最原始的方法,跑junit用例的时候,发现此处存在性能瓶颈。最后使用了jdk中自带的二分搜索,满足了性能要求。呵呵,二分查找确实很快。下面附上Arrays.binarySearch()的JDk源代码

/**
	 * 
	 * @param a          已经排好序的数组
	 * @param fromIndex  搜索范围的起始位置(包含)
	 * @param toIndex    搜索范围的结束位置(不包含)
	 * @param key        需要查询的关键字
	 * @return
	 *        如果key包含在数组中,则返回对应的数组索引;
	 *        否则返回 (-(插入点) - 1).
	 *        
	 * 插入点 被定义为将键插入数组的那一点:即第一个大于此键的元素索引,如果数组中的所有元素都小于指定的键,则为 a.length
	 */
    private static int binarySearch(int[] a, int fromIndex, int toIndex,int key) 
    {
    	int low = fromIndex;
    	int high = toIndex - 1;

    	while (low <= high)
    	{
    		//int mid = (low + high) / 2;
    		//System.out.println((2+7) >>> 1);//4
    		//System.out.println((2+5) >>> 1);//3
		    int mid = (low + high) >>> 1;
		    
		    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.
    }

 

       其实JDK的api提供了很多工具方法,学会之后,能够提高我们对java语言的熟悉程度和算法能力,毕竟JDK的算法,大部分性能还是很高的

Arrays.binarySearch()

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号