python——二分法

目录

• 一、算法——二分法
  • 二分法（算法的一种，算法是解决问题的方法）可以极大低缩小问题规模
    • 案例：从一个按照从小到大排列的数字列表中找到指定的数字
    • 方案一：遍历的效率太低
    • 方案二：二分法

一、算法——二分法

二分法（算法的一种，算法是解决问题的方法）可以极大低缩小问题规模

案例：从一个按照从小到大排列的数字列表中找到指定的数字

方案一：遍历的效率太低

nums=[-3,4,7,13,17,21,27,98,102,108]
find_num=102

for num in nums:
    if num==find_num:
        print('find it')
        break

方案二：二分法

nums = [11,12,23,25,26,27,38,45,48,49,56,78,89,102,108]

def search(find_num,nums):
    print(nums)
    if len(nums) == 0:
        print('not exists')
        return
    mid_index = len(nums) // 2

    if find_num > nums[mid_index]:
        new_nums = nums[mid_index +1:]
        search(find_num,new_nums)
    elif find_num < nums[mid_index]:
        new_nums = nums [:mid_index]
        search(find_num,new_nums)
    else:
        print('find it')

# search(102,nums)
# search(45,nums)
# search(23,nums)


# search(28,nums)
# search(77,nums)