因为要精确到后六位，可以先用二分查找出整数位，然后再二分查找小数第一位，第二位，到第六位。

整数查找很简单，判断当前数小于+1后大于即可找到，

小数查找举查找小数后第一位来说，从x.0到(x+1).0，查找终止条件与整数一样，当前数小于，加0.1大于，

后面的位数以此类推，可以用x*10^(-i)通项来循环或者递归，终止条件是i>6，

想了一下复杂度，每次二分是logn，包括整数位会查找7次，所以时间复杂度为7logn。空间复杂度没有开辟新的储存空间，空间复杂度为1。

没有具体用代码实现，只是思路，还请多多指正。之后会用js去实际实现。

二分法求一个数x的平方根y？
解答：根据x的值，判断求解值y的取值范围。假设求解值范围min < y < max。若0<x<1，则min=x，max=1；若x=1，则y=1；x>1，则min=1，max=x；在确定了求解范围之后，利用二分法在求解值的范围中取一个中间值middle=(min+max)÷2，判断middle是否是x的平方根？若(middle+0.000001)*(middle+0.000001)＞x且(middle-0.000001)*(middle-0.000001)<x，根据介值定理，可知middle既是求解值;若middle*middle > x，表示middle＞实际求解值，max=middle; 若middle*middle ＜ x，表示middle＜实际求解值，min =middle;之后递归求解！
备注：因为是保留6位小数，所以middle上下浮动0.000001用于介值定理的判断

1、low=mid+1，high=mid-1 学习了比较严谨条件


2、二分法求根号5

a:折半：       5/2=2.5

b:平方校验:  2.5*2.5=6.25>5，并且得到当前上限2.5

c:再次向下折半:2.5/2=1.25

d:平方校验：1.25*1.25=1.5625<5,得到当前下限1.25

e:再次折半:2.5-(2.5-1.25)/2=1.875

f:平方校验：1.875*1.875=3.515625<5,得到当前下限1.875

每次得到当前值和5进行比较，并且记下下下限和上限，依次迭代，逐渐逼近平方根：

求平方根，可以参考0到99之间猜数字的思路，99换成x, 循环到误差允许内即可，注意1这个分界线。欢迎交流，Java如下
    public static double sqrt(double x, double precision) {
        if (x < 0) {
            return Double.NaN;
        }
        double low = 0;
        double up = x;
        if (x < 1 && x > 0) {
            /** 小于1的时候*/
            low = x;
            up = 1;
        }
        double mid = low + (up - low)/2;
        while(up - low > precision) {
            if (mid * mid > x ) {//TODO mid可能会溢出
                up = mid;
            } else if (mid * mid < x) {
                low = mid;
            } else {
                return mid;
            }
            mid = low + (up - low)/2;
        }
        return mid;
    }

def sqrt(x):
    '''
    求平方根，精确到小数点后6位
    '''
    low = 0
    mid = x / 2
    high = x
    while abs(mid ** 2 - x) > 0.000001:
        if mid ** 2 < x:
            low = mid
        else:
            high = mid
        mid = (low + high) / 2
    return mid

总结：二分查找（上）
一、什么是二分查找？
二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。
二、时间复杂度分析？
1.时间复杂度
假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2^k)，…，这是一个等比数列。当n/(2^k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。
2.认识O(logn)
①这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？
②因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。
③由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。
三、如何实现二分查找？
1.循环实现
代码实现：
public int binarySearch1(int[] a, int val){
    int start = 0;
    int end = a.length - 1;
    while(start <= end){
        int mid = start + (end - start) / 2;
        if(a[mid] > val) end = mid - 1;
        else if(a[mid] < val) start = mid + 1;
        else return mid;
    }
    return -1;
}
注意事项：
①循环退出条件是：start<=end，而不是start<end。
②mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因为如果start和end比较大的话，求和可能会发生int类型的值超出最大范围。为了把性能优化到极致，可以将除以2转换成位运算，即start + ((end - start) >> 1)，因为相比除法运算来说，计算机处理位运算要快得多。
③start和end的更新：start = mid - 1，end = mid + 1，若直接写成start = mid，end=mid，就可能会发生死循环。
2.递归实现
public int binarySearch(int[] a, int val){
    return bSear(a, val, 0, a.length-1);
}
private int bSear(int[] a, int val, int start, int end) {
    if(start > end) return -1;
    int mid = start + (end - start) / 2;
    if(a[mid] == val) return mid;
    else if(a[mid] > val) end = mid - 1;
    else start = mid + 1;
    return bSear(a, val, start, end);
}
四、使用条件（应用场景的局限性）
1.二分查找依赖的是顺序表结构，即数组。
2.二分查找针对的是有序数据，因此只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
3.数据量太小不适合二分查找，与直接遍历相比效率提升不明显。但有一个例外，就是数据之间的比较操作非常费时，比如数组中存储的都是长度超过300的字符串，那这是还是尽量减少比较操作使用二分查找吧。
4.数据量太大也不是适合用二分查找，因为数组需要连续的空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间。
五、思考
1.如何在1000万个整数中快速查找某个整数？
①1000万个整数占用存储空间为40MB，占用空间不大，所以可以全部加载到内存中进行处理；
②用一个1000万个元素的数组存储，然后使用快排进行升序排序，时间复杂度为O(nlogn)
③在有序数组中使用二分查找算法进行查找，时间复杂度为O(logn)
2.如何编程实现“求一个数的平方根”？要求精确到小数点后6位？

开篇的问题：1000w 个 8字节整数的中查找某个整数是否存在，且内存占用不超过100M ？ 我尝试延伸了一些解决方案：
1、由于内存限制，存储一个整数需要8字节，也就是 64 bit。此时是否可以考虑bitmap这样的数据结构，也就是每个整数就是一个索引下标，对于每一个索引bit，1 表示存在，0 表示不存在。同时考虑到整数的数据范围，8字节整数的范围太大，这是需要考虑压缩的问题，压缩方案可以参考 RoaringBitmap 的压缩方式。
2、我们要解决的问题，也就是判断某个元素是否属于某个集合的问题。这里是否可以和出题方探讨是否严格要求100%判断正确。在允许很小误差概率的情景下（比如判断是否在垃圾邮件地址黑名单中），可以考虑 BloomFilter 。
BloomFilter 存储空间更加高效。1000w数据、0.1%的误差下需要的内存仅为 17.14M
时间复杂度上，上面两种都是 hashmap的变种，因此为 o(1)。

关于求平方根的题，我知道一种比较巧妙的方法，那就是利用魔数，时间复杂度是 O(1)，根据我测试，精度大概能精确到 5 位小数，也还不错。下面是 c 语言代码

float q_rsqrt(float number) {
    int i;
    float x2, y;
    const float threehalfs = 1.5;
    x2 = number * 0.5;
    y = number;
    i = *(int*)&y;
    i = 0x5f3759df - (i >> 1);
    y = *(float*)&i;
    y = y * (threehalfs - (x2 * y * y));
    y = y * (threehalfs - (x2 * y * y));
    y = y * (threehalfs - (x2 * y * y));

    return 1.0 / y;
}

关于1000万数中快速查找某个整数，我有个想法。考虑用数组下标来存储数据，一个bit位来存储标记。第一次排序的时候能得到这组数的最大值和最小值。 假如最小是5，最大是2000万。那我们定义一个字节数组Byte arr[2000万]，因为我只需要打标记，所以一个bit能存下标记，一个byte能存8个数。只需要2MB多一点就能存2000万个数的状态（存在还是不存在）
先把这1000万个数存进去，用数x/8得到下标。用数x%8得到余数，因为每8个数一组得到的数组下标相同，所以还需要通过余数来确定具体是哪一个数。之后开始设置状态，从低位到高位，每一位代表一个数的状态，case0到7，每一次设置当下号码的状态时，先用按位于计算把其他不相关位置为1，当前位置为0，然后按位或对当前位置设置状态。存在就设置位1 ，不存在就设置位0
上述操作执行完之后，就支持任意查找了。只需要输入一个数x，我就能立刻通过x/8和x%8得到当前这个数的位置，然后把这个位置的状态位数字取出来。如果是1表示存在，如果是0表示不存在。
不知道这个想法有没有什么漏洞。希望老师或者一起学习的同学能帮忙一起想想

/**
     * 求一个数的平方根
     *
     * @param n：待求的数
     * @param deltaThreshold 误差的阈值
     * @return
     */
    public static double getSqureRoot(int n, double deltaThreshold) {
        double low = 1.0;
        double high = (double) n;
        while (low <= high) {
            double mid = low + ((high - low) / 2);
            double square = mid * mid;
            double delta = Math.abs(square / n - 1);
            if (delta < deltaThreshold) {
                return mid;
            } else if (square < n) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return -1.0;
    }

平方根C代码，precision位数，小数点后6位是0.000001
double squareRoot(double a , double precision){
    double low,high,mid,tmp;
    if (a>1){
        low = 1;
        high = a;
    }else{
        low = 1;
        high = a;
    }
    while (low<=high) {
        mid = (low+high)/2.000;
        tmp = mid*mid;
        if (tmp-a <= precision && tmp-a >= precision*-1){
            return mid;
        }else if (tmp>a){
            high = mid;
        }else{
            low = mid;
        }
    }
    return -1.000;
}
int main(int argc, const char * argv[]) {
    double num = squareRoot(2, 0.000001);
    printf("%f",num);
    return 0;
}

链表的二分查找，每次查找的时间复杂度都为当前数据规模的一半，所以最坏情况下：
查找次数f(n) = n + n/2 + n/4 + n/8 + ... + 1 = n(1 + 1/2 + 1/4 + ... 1/n)

情况1： n = 2^k, 根据等比数列公式 f(n) = 2^k * ( 1 - (1/2) ^k) / (1 - 1/2) = 2n - 1
情况2：n != 2^k, 假设k无穷大，则limf(n) = n ( 1 / (1 - 1/2)) = 2n, 实际上k < +∞， 所以
f(n) < lim f(n) = 2n => f(n) = 2n-1

综上所述，f(n) = 2n - 1, 时间复杂度为O(n)

二分查找Python实现：
1、非递归方式
def bsearch(ls, value):
    low, high = 0, len(ls)-1
    while low <= high:
        mid = low + (high - low) // 2
        if ls[mid] == value:
            return mid
        elif ls[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return -1

2、递归方式
def bsearch(ls, value):
    return bsearch_recursively(ls, 0, len(ls)-1, value)
    
def bsearch_recursively(ls, low, high, value):
    if low > high:
        return -1
    mid = low + (high - low) // 2
    if ls[mid] == value:
        return mid
    elif ls[mid] < value:
        return bsearch_recursively(ls, mid+1, high, value)
    else:
        return bsearch_recursively(ls, low, mid-1, value)