4、作业：插入排序和二分查找

# 作业

1、完整课程知识整理
2、插入排序
3、二分查找
    提示：mid = (high + low) / 2 (整除)
    mid为索引

插入排序

'''
nums = [6, 4, 3, 5, 7, 2, 10, 9]

第一个数值不动，第二个数值与第一个比较

第一次
=> nums = [4, 6, 3, 5, 7, 2, 10, 9]

第二次
=> nums = [4, 3, 6, 5, 7, 2, 10, 9]

第三次
=> nums = [3, 4, 6, 5, 7, 2, 10, 9]
.
.
.
结束条件，前面比后面小，或者索引为0（前面没有元素）
'''


nums = [6, 4, 3, 5, 7, 2, 10, 9]

# 第一个数值不动，依次后面的与前面的数值倒序对比。
for i in range(1, len(nums)):
    for j in range(i, 0, -1):
        if nums[j] < nums[j - 1]:
            nums[j], nums[j - 1] = nums[j - 1], nums[j]
        else:
            break
        print(nums)

二分查找

'''
# 二分查找：必须是一个有序的list。
1、确定list的中间值：(end + start) // 2
    如果比中间值大或者小，再进行查找中间值
2、
第一次：start=0 end=len(nums)-1 middle=(end_num + start_num) // 2
find_num > nums[middle]
    start = middle + 1
    end = len(nums) - 1


find_num < nums[middle]
    end = middle -1
    start = 0

2、结束条件：
    找到了
    或者end<start
'''

nums = [6, 11, 24, 32, 12, 16, 15, 13]
# 保证list有序
nums.sort()
print(nums)
find_num = input("Please input your numbers:")
find_num = int(find_num)
start_num = 0
end_num = len(nums) - 1
middle = (end_num + start_num) // 2
while True:
    if find_num > nums[middle]:
        start_num = middle + 1
        middle = (end_num + start_num) // 2
    elif find_num < nums[middle]:
        end_num = middle - 1
        middle = (end_num + start_num) // 2
    else:
        print("你输入数字的索引：", middle)
        break
    if end_num < start_num:
        break