二分查找 BinarySearch

1.我写的代码

测试数据来自维基百科

二分搜索

public class BinarySearch {
     public  static    int arry[]  = {1,3,4,6,7,8,10,13,14};

    public static void main(String[] args) {
        System.out.println(bs(0,arry.length-1,4));
    }
    static boolean  bs(int start,int end,int key)
    {
        if(start>end)  return  false;
        int middle =(start + end) >>> 1;  //int middle =  (start+end)/2;
        if(key==arry[middle])
        {
            System.out.println("所在位置:"+middle);
            return  true;
        }
        if(key<arry[middle])  return  bs(start,middle-1,key);
        if(key>arry[middle])  return  bs(middle+1,end,key);
        return false;
    }
}

2.时间复杂度，空间复杂度的分析

二分查找递归查找数组的剩余长度依次为 n 、n/2 、 n/4、n/8.....n/(2^k)
其中 n/(2^k) == 1 k=log2(n)=logn/log2 所以平均时间复杂度为logn