常见算法之9---折半查找（二分查找）

思想：将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

分析：它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。

代码：

public static boolean find(int n, int[] a, int start, int end) {
　　if (start > end)
　　　　return false;

　　int mid = (start + end) / 2;
　　if (n == a[mid])
　　　　return true;
　　else {
　　　　if (n > a[mid])
　　　　　　return find(n, a, mid + 1, end);
　　　　else
　　　　　　return find(n, a, start, mid - 1);
　　}
}

注：对于这种简单常见的代码，应该一次写成。