问题描述：给定数组a[0 : 8]={1, 8, 12, 15, 16, 21, 30, 35, 39}。采用二分搜索算法完成下述任务：当待搜索元素x=10不在数组中时，返回小于 x 的最大元素位置 i 和大于 x 的最小元素位置 j 。

变量定义:左指针lo，右指针hi，中间指针mid

解决方案：找不到x可以分两种情况讨论：
<1>lo的位置在hi的右边，即lo>hi，那么这时hi的位置就是小于 x 的最大元素位置 i ，而lo的位置就是大于 x 的最小元素位置 j
<2>lo与hi位置相同，那么这个元素如果比x大，那i的位置在这个位置的前一个，如果这个元素比x小，那么j的位置在他的后一个。 

package search;

public class BinarySearch {

    public static int binary(int[] a,int lo,int hi,int n) {
        int i=0,j=0;         //小于n的最大元素位置i,大于n的最小元素位置j
        while(lo<hi) {
            int mid=(lo+hi)/2; //当lo>hi时，循环跳出，这时lo指针的位置就是大于n的最小元素位置j,hi指针     
            if(a[mid]<n) {lo=mid+1; j=lo;}  //的位置即小于n的最大元素位置
            else if(a[mid]>n) {hi=mid-1; i=hi;}
            else
                return mid;
        }
        if(lo==hi) {    //如果lo和hi指针指向同一个元素就会存在以下两种情况     
            if(a[lo]>n) i=j-1;  //如果指向的这个元素大于n说明它的前一个元素即小于n的最大元素
            else if(a[lo]<n) j=i+1;  //如果指向的这个元素小于n说明它的后一个元素即大于n的最小元素
        }
        System.out.print(i+","+j);
        return -1;
    }



    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] a= {1, 8, 12, 15, 16, 21, 30, 35, 39};
        int hi=a.length-1;
        binary(a,0,hi,10);
    }

}