二分查找

public class TestBinSearch {

	public static void main(String[] args) {

		int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

		System.out.println(binSearch(a, 0, a.length - 1, 100));
	}

	// 二分查找递归实现
	public static int binSearch(int a[], int start, int end, int key) {

		int middle= (end - start) / 2 + start;
		if (a[middle] == key) {
			return middle;
		}
		if (start >= end) {
			return -1;

		} else if (a[middle] < key) {
			return binSearch(a, middle+ 1, end, key);
		} else if (a[middle] > key) {
			return binSearch(a, start, middle- 1, key);
		}
		return -1;

	}

	// 二分查找普通循环实现
	public static int binSearch(int a[], int key) {

		int middle= a.length / 2;
		if (key == a[middle]) {
			return middle;
		}

		int start = 0;
		int end = a.length - 1;
		while (start <= end) {
			middle= (end - start) / 2 + start;

			if (key < a[middle]) {

				end = middle- 1;
			} else if (key > a[middle]) {

				start = middle+ 1;
			} else {
				return middle;
			}
		}
		return -1;
	}
}