Arrays.binarySearch()

      最近做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的算法，大部分性能还是很高的