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

承接上一篇：查找：顺序查找与二分法查找，将二分法更多详细的python实现解题写下笔记。

简单方法

'''

二分法查找在列表中的用户输入值，返回index

三种情况跳出循环体： LR相邻    LR位置重合   RL

算法时间复杂度为O(logn)

'''

def bi_search(lis,num):

    if len(lis) == 0:           #判断边界条件

        return -1

　　

    left, right = 0, len(lis)-1          #列表的起始点和终点

    while left <= right:

        mid = (left + (right - left)) // 2     #取二分中心点，或 mid = (left + right) // 2

        if num < lis[mid]:               #右点左移

            right = mid - 1

        elif num > lis[mid]:             #左点右移

            left = mid + 1

        else:                            #num == lis[mid]

            return mid

    return -1

num = int(input('please input a num:'))

alist = [1,2,3,4,5,6,7,8]

bi_search(alist,num)

输出结果：

please input a num:3

2

改进方案：如果我要找一个数组中相同数字最前面的那个数字。比如lis = [1,2,2,2,2,3,3,5,6],用上面的代码会返回index为4，下面代码解决如何返回相同元素的最前一个

经典方法

'''

改进版本经典方法，这种方法更加好写

把常规方法的right = mid -1 和left = mid +1修改

找不到返回-1

'''

def bi_search2(lis, num):

    #这个程序中这一条判断边界非常重要

    if len(lis) == 0:

        return -1

    #判断二分条件

    left, right = 0, len(lis) - 1

    while left + 1 < right:

        mid = left + (right - left) // 2

        if lis[mid] == num:

            right = mid

        elif lis[mid] < num:

            left = mid

        elif lis[mid] > num:

            right = mid

    #在这里返回

    if lis[left] == num:

        return left

    if lis[right] == num:

        return right

    return -1

num = int(input('please input a num:'))

alist = [1,2,2,2,2,6,7,8]

bi_search2(alist,num)

#输出结果

please input a num: 2

1

下面类型有针对旋转数组的搜索方法，先来介绍一下旋转数组的定义：

旋转数组：

将包含 n 个元素的数组向右旋转 k 步；例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

以下为更多的使用二分检索的类型：

查找旋转数组中的最小值

'''

查找旋转数组中的最小值

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

'''

查找旋转数组的指定值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

巴特西