Cacher is the code snippet organizer for pro developers

# 终止条件、区间上下界更新方法、返回值选择

# 1. 最简单的情况，假定有序且无重复元素，快速找出元素位置（数组一定存在该元素）
# 循环实现二分查找，可以作为模版用，针对不同的哟求，设定不同边界条件
# 比如 循环结束条件中 left 和 right 的关系，更新 left 和 right 位置时要不要加 1 减 1。
def bsearch1(arr, val):
    low = 0
    high = len(arr) - 1
    while low <= high:
        # 计算中间位置的几种写法
        # 1. 常见写法：mid = (low + high) // 2
        # 缺陷：如果low和high都比较大话，两者之和就有可能溢出  
        # 2. 更好的写法:
        mid = low + (high-low)//2
        # 3. 性能极限优化的写法：将除法运算换成位运算
        # 因为相对于除法运算，计算机处理位运算要快得多，左移一位都相当于除以2的1次方
        # 换成位运算优先级降低，一定要加括号!!!!
        # mid = low + ((high-low) >> 1)
        
        # print('low={0}, high={1}, mid={}'.format(low, high, mid))
        if arr[mid] < val:   # 小于val说明真正的val还在mid右边，所以重设low=mid+1
            low = mid + 1 
        elif arr[mid] > val: # 大于val说明真正的val还在mid左边，所以重设high=mid-1
            high = mid - 1
        else:
            return mid
    return -1

# 递归实现二分查找
    # 递归思路
    # 1.找到任务的相似性，进行划分
    # 2. 设置出口，制定一个循环终止点(出口就是递归到不满足相似性条件的地方)
def bsearch1_(arr, val):
    low = 0 
    high = len(arr)
    return bsearchInternally(arr, low, high, val)

def bsearchInternally(arr, low, high, val):
    if low > high:
        return -1 
    
    mid = low + ((high - low) >> 1)
    if arr[mid] == val:
        return mid
    elif arr[mid] < val:
        low = mid + 1
    else:
        high = mid - 1
    return bsearchInternally(arr, low, high, val)

# 2. 变体1 查找第一个值等于给定值的元素
def bsearch2(arr, val):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = low + (high-low)//2
        # print('low={0}, high={1}, mid={2}'.format(low, high, mid))
        if arr[mid] < val:
            low = mid + 1 
        elif arr[mid] > val:
            high = mid - 1
        else:
            if mid==0 or arr[mid-1] != val:  # 等于mid时，多加一层条件判断
                return mid
            else:
                high = mid - 1 
    return -1

# 3. 变体2 查找最后一个值等于给定值的元素
def bsearch3(arr, val):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = low + (high-low)//2
        if arr[mid] < val:
            low = mid + 1 
        elif arr[mid] > val:
            high = mid - 1
        else:
            if mid==len(arr)-1 or arr[mid+1] != val:  # 等于mid时，多加一层条件判断
                return mid
            else:
                low = mid + 1 
    return -1


# 4. 变体3 查找第一个大于等于给定值的元素
# 这个变体和搜索插入位置的问题本质是一样的，不过那个假定没有重复元素，跳出循环返回Low就行
# 下面的代码也适用搜索插入位置
def bsearch4(arr, val):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = low + (high-low)//2
        if arr[mid] < val:
            low = mid + 1 
        else:
            # 对于 a[mid] 大于等于给定值 value 的情况，我们要先看下这个 a[mid] 是不是我们要找的
            # 第一个值大于等于给定值的元素。如果 a[mid] 前面已经没有元素，或者前面一个元素小于
            # 要查找的值 value，那 a[mid] 就是我们要找的元素。
            if mid==0 or arr[mid-1] < val:
                return mid
            else:
                high = mid - 1
    return -1

# 5. 变体4 查找最后一个小于等于给定值的元素
def bsearch6(arr, val):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = low + (high-low)//2
        if arr[mid] > val:
            high = mid - 1 
        else:
            if mid==len(arr)-1 or arr[mid+1] > val:
                return mid
            else:
                low = mid + 1
    return -1

# 6. 求平方根，精确到小数点后6位
# https://www.jianshu.com/p/e72bb73f26bd
# 二分查找实现
def sqrt1(x: int) -> int:
    if x < 2:
        return x
    low, high = 1.0, x
    mid = low + (high - low) / 2.0
    num = mid * mid
    #if 2.0 <= 1e-6
    # while low <= high:
    while abs(num - x) > 1e-6:
        # print('low={0}, high={1}, mid={2}, num={3}'.format(low, high, mid, num))
        if num < x:
            low = mid #因为是精确到小数位，这里不能+1操作了，否则一下蹦走了
        else:
            high = mid 
        # else:
        #     return mid  # 因为从1开始，几乎不会有数字的能够直接 num == x， 这一项可以省略
        mid = low + (high - low) / 2.0
        num = mid * mid
        # 注意，这里实际上是计算精确到小数点后6位，而不是小数点后面有6位
    # 可以对结果对6位四舍五入
    return round(mid, 6) # or mid 

# TODO 需复习对应背景知识 OneNote.北冥有鱼.LC.牛顿法
# 牛顿迭代法实现, 和泰勒级数以及求最优化方法的原理是一样的，
def sqrt2(x):
   y = 1.0
   while abs(y * y - x) > 1e-6:
       y = (y + x/y)/2
   return y

arr1 = [3, 4, 10, 18, 30, 36]
arr2 = [1, 2, 4, 4, 6, 6, 8]
arr3 = [1, 2, 3]
arr4 = [-1, 0, 4, 8, 20]
arr5 = [1,3,5,6]

for i in range(10):
    print(sqrt2(i))


# 二分查找经典LeetCode
# 35. 搜索插入位置
# 69. x的平方根
# 33. 搜索旋转排序数组