二分查找

android 和openJdk的实现

	// 以下代码来自 openJDK ./jdk/src/share/classes/java/util/Arrays.java
	private static void rangeCheck(int length, int fromIndex, int toIndex) {
		if (fromIndex > toIndex) {
			throw new IllegalArgumentException("fromIndex(" + fromIndex
					+ ") > toIndex(" + toIndex + ")");
		}
		if (fromIndex < 0) {
			throw new ArrayIndexOutOfBoundsException(fromIndex);
		}
		if (toIndex > length) {
			throw new ArrayIndexOutOfBoundsException(toIndex);
		}
	}

	/**
	 * Searches the specified array of ints for the specified value using the
	 * binary search algorithm. The array must be sorted (as by the
	 * {@link #sort(int[])} method) prior to making this call. If it is not
	 * sorted, the results are undefined. If the array contains multiple
	 * elements with the specified value, there is no guarantee which one will
	 * be found.
	 * 
	 * @param a
	 *            the array to be searched
	 * @param key
	 *            the value to be searched for
	 * @return index of the search key, if it is contained in the array;
	 *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
	 *         <i>insertion point</i> is defined as the point at which the key
	 *         would be inserted into the array: the index of the first element
	 *         greater than the key, or <tt>a.length</tt> if all elements in the
	 *         array are less than the specified key. Note that this guarantees
	 *         that the return value will be &gt;= 0 if and only if the key is
	 *         found.
	 */
	public static int binarySearch(int[] a, int key) {
		return binarySearch0(a, 0, a.length, key);
	}

	/**
	 * Searches a range of the specified array of ints for the specified value
	 * using the binary search algorithm. The range must be sorted (as by the
	 * {@link #sort(int[], int, int)} method) prior to making this call. If it
	 * is not sorted, the results are undefined. If the range contains multiple
	 * elements with the specified value, there is no guarantee which one will
	 * be found.
	 * 
	 * @param a
	 *            the array to be searched
	 * @param fromIndex
	 *            the index of the first element (inclusive) to be searched
	 * @param toIndex
	 *            the index of the last element (exclusive) to be searched
	 * @param key
	 *            the value to be searched for
	 * @return index of the search key, if it is contained in the array within
	 *         the specified range; otherwise,
	 *         <tt>(-(<i>insertion point</i>) - 1)</tt>. The <i>insertion
	 *         point</i> is defined as the point at which the key would be
	 *         inserted into the array: the index of the first element in the
	 *         range greater than the key, or <tt>toIndex</tt> if all elements
	 *         in the range are less than the specified key. Note that this
	 *         guarantees that the return value will be &gt;= 0 if and only if
	 *         the key is found.
	 * @throws IllegalArgumentException
	 *             if {@code fromIndex > toIndex}
	 * @throws ArrayIndexOutOfBoundsException
	 *             if {@code fromIndex < 0 or toIndex > a.length}
	 * @since 1.6
	 */
	public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
		rangeCheck(a.length, fromIndex, toIndex);
		return binarySearch0(a, fromIndex, toIndex, 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;
			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.
	}

	// 以下代码来自android
	// http://androidxref.com/5.0.0_r2/xref/frameworks/base/core/java/android/util/ContainerHelpers.java
	// This is Arrays.binarySearch(), but doesn't do any argument validation.
	public static int binarySearch(int[] array, int size, int value) {
		int lo = 0;
		int hi = size - 1;

		while (lo <= hi) {
			final int mid = (lo + hi) >>> 1;
			final int midVal = array[mid];

			if (midVal < value) {
				lo = mid + 1;
			} else if (midVal > value) {
				hi = mid - 1;
			} else {
				return mid; // value found
			}
		}
		return ~lo; // value not present
	}

相关属性

• 数组是有序的
• 时间复杂度是log(n)
• 亮点是没查到时的返回值，(-insertion point - 1)