Python算法之二分法

算法：是高效解决问题的办法
　需求：有一个按照从小到大顺序排列的数字列表
　　　需要从该数字列表中找到我们想要的那个一个数字
　　　如何做更高效？？？

# 如何将一个列表按从小到大的顺序排
nums=[-3,4,13,10,-2,7,89]
nums.sort()
print(nums)

　方案一：整体遍历效率太低

nums=[-3,4,7,10,13,21,43,77,89]
find_num=10
for num in nums:
    if num == find_num:
        print('find it')
        break

　方案二：二分法

# 算法思想
def binary_search(find_num,列表):
    mid_val=找列表中间的值
    if find_num > mid_val:
        # 接下来的查找应该是在列表的右半部分
        列表=列表切片右半部分
        binary_search(find_num,列表)
    elif find_num < mid_val:
        # 接下来的查找应该是在列表的左半部分
        列表=列表切片左半部分
        binary_search(find_num,列表)
    else:
        print('find it')

二分法代码实现：

# 递归法：
def binary_search(ls, num, lower=0, high=None):
    if high is None:
        high = len(ls) - 1
    mid = (lower + high) // 2
    if mid == 0 and num != ls[0]:
        return "不存在"
    if mid == len(ls) - 1 and num != ls[-1]:
        return "不存在"

    if num == ls[mid]:
        return mid, ls[mid]
    elif num < ls[mid]:
        return binary_search(ls, num, lower, mid)
    else:
        return binary_search(ls, num, mid + 1, high)

nums=[-3,4,7,10,21,43,77,89,123]
print(binary_search(nums,-3))

# 递推法
def binary_search(ls, num):
    low = 0
    high = len(ls) - 1
    while low <= high:
        mid = (low + high) // 2
        if num == ls[mid]:
            return mid, ls[mid]
        elif num < ls[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return 


nums=[-3,4,7,10,21,43,77,89,123]
print(binary_search(nums,125)) # 不存在，返回None

编程思想

面向过程的编程思想：

　　核心是"过程"二字，过程即流程，指的是做事的步骤：先什么、再什么、后干什么

　　基于该思想编写程序就好比在设计一条流水线

优点：复杂的问题流程化、进而简单化

缺点：扩展性非常差

面向过程的编程思想应用场景解析：

　　1、不是所有的软件都需要频繁更迭：比如编写脚本

　　2、即便是一个软件需要频繁更迭，也不并不代表这个软件所有的组成部分都需要一起更迭