查找算法：二分查找及其 python 实现的案例研究

'''
查找旋转数组中的最小值
python自带min()算法时间复杂度为O(n)
比这个更好的时间复杂度方法就是二分法了O(lgn)
'''

#O(nlgn)
def searchlazy(alist):
    alist.sort()
    return alist[0]

#O(n)
def searchslow(alist):
    mmin = alist[0]
    for i in alist:
        mmin = min(mmin, i)
    return mmin 
        
#O(lgn)
def search(alist):
    #第一步
    if len(alist) == 0:
        return -1    
    left, right = 0, len(alist) - 1
    
    #第二步
    while left + 1 < right: 
        if (alist[left] < alist[right]):
            return alist[left];
        mid = left + (right - left) // 2
        
        #第三步
        if (alist[mid] >= alist[left]):
            left = mid + 1
        else:
            right = mid
    
    #第四步
    return alist[left] if alist[left] < alist[right] else alist[right]

num = int(input('please input a num:'))
alist = [3,4,5,6,7,1,2]
search(alist)

#输出结果
please input a num:4
1

'''
查找旋转数组的指定值target
O(lgn)
'''
def search(alist, target):
    
    #第一步
    if len(alist) == 0:
        return -1    
    left, right = 0, len(alist) - 1
    
    #第二步
    while left + 1 < right: 
        mid = left + (right - left) // 2
        
        #第三步
        if alist[mid] == target:
            return mid
        
        #判断当mid前半部分排好序的
        if (alist[left] < alist[mid]):
            #判断target的位置决定mid的赋值
            if alist[left] <= target and target <= alist[mid]:
                right = mid
            else:
                left = mid
        #mid后半部分
        else:
            if alist[mid] <= target and target <= alist[right]:
                left = mid
            else: 
                right = mid
    #第四步                        
    if alist[left] == target:
        return left
    if alist[right] == target:
        return right
        
    return -1

num = int(input('please input a num:'))
alist = [3,4,5,6,7,1,2]
search(alist,num)

#输出结果
please input a num:4
1

'''
搜索插入位置
给定一个有序数组和目标值，查找数组该值返回Index，否则返回应该被插入的位置Index
用for循环一个个找为O(n)，以下二分法为O(lgn)更优
'''
def search_insert_position(alist, target):
    
    #第一步
    if len(alist) == 0:
        return 0  
    left, right = 0, len(alist) - 1
    
    #第二步
    while left + 1 < right: 
        mid = left + (right - left) // 2
        
        #第三步
        if alist[mid] == target:
            return mid
        
        if (alist[mid] < target):
            left = mid
        else:
            right = mid
    
    #第四步        
    if alist[left] >= target:
        return left
    if alist[right] >= target:
        return right
        
    return right + 1

num = int(input('please input a num:'))
alist = [3,4,5,6,7,8,9]
search_insert_position(alist,num)

#输出结果
please input a num:4
1

'''
搜索一个区间
找到一个给定目标值的起始和结束位置
'''
def search_range(alist, target):
    if len(alist) == 0:
        return (-1, -1)  
    
    lbound, rbound = -1, -1

    # search for left bound 
    left, right = 0, len(alist) - 1
    while left + 1 < right: 
        mid = left + (right - left) // 2
        if alist[mid] == target:
            right = mid
        elif (alist[mid] < target):
            left = mid
        else:
            right = mid
            
    if alist[left] == target:
        lbound = left
    elif alist[right] == target:
        lbound = right
    else:
        return (-1, -1)

    # search for right bound 
    left, right = 0, len(alist) - 1        
    while left + 1 < right: 
        mid = left + (right - left) // 2
        if alist[mid] == target:
            left = mid
        elif (alist[mid] < target):
            left = mid
        else:
            right = mid
            
    if alist[right] == target:
        rbound = right
    elif alist[left] == target:
        rbound = left
    else:
        return (-1, -1)        
        
    return (lbound, rbound)

num = int(input('please input a num:'))
alist = [3,4,5,6,7,8,9,10,14,15]
search_range(alist,num)

#输出结果
please input a num:6
(3, 3)

'''
在无限序列中找到某元素出现的第一个位置
'''

def search_first(alist):
    left, right = 0, 1
    
    while alist[right] == 0:
        left = right
        right *= 2
        
        if (right > len(alist)):
            right = len(alist) - 1
            break
    
    #这里为1
    return left + search_range(alist[left:right+1], 1)[0]

alist = [0, 0, 0, 0, 0, 1]
r = search_first(alist)
print(r)

#输出结果
5

'''
给定一个包含N+ 1整数的数组NUM，其中每个整数在1和N之间（包含），证明至少有一个重复的数字必须存在。假设只有一个重复的数字，找到重复的数字。
注：
您不必修改数组（假定数组是只读的）。
你必须只使用常数，O(1)额外的空间。
您的运行时复杂性应该小于O（n2）。
在数组中只有一个重复的数字，但是它可以重复不止一次。
'''

def findDuplicate(nums):

    low = 1
    high = len(nums)-1

    while low < high:
        mid = low + (high - low) // 2
        count = 0
        for i in nums:
            if i <= mid:
                count+=1
        if count <= mid:
            low = mid+1
        else:
            high = mid
    return low

nums = [3,5,6,3,1,4,2]
findDuplicate(nums)

#输出结果
3

'''
供暖设备案例
设计一款有固定供暖半径的供暖设备来给所有房屋供暖
输入每个房屋和每个供暖设备的位置，输出供暖设备的最小半径

'''
from bisect import bisect

def findRadius(houses, heaters):
    heaters.sort()
    ans = 0

    for h in houses:
        hi = bisect(heaters, h)
        left = heaters[hi-1] if hi - 1 >= 0 else float('-inf')
        right = heaters[hi] if hi < len(heaters) else float('inf')
        ans = max(ans, min(h - left, right - h))

    return ans

houses = [1,2,3,4]
heaters = [1,4]
f1 = findRadius(houses, heaters)
print(f1)

houses2 = [1,12,23,34]
heaters2 = [12,24]
f2 = findRadius(houses2, heaters2)
print(f2)

#输出结果
1
11