双指针问题----二分法查找

首先先普及一下算法的特性

算法有五大特性：
可行性： 算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
有穷性： 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
输入： 算法具有0个或多个输入
输出： 算法至少有1个或多个输出
确定性（无二义性）：算法中的每一步都有确定的含义，不会出现二义性

算法的时间复杂度计算：

最优时间复杂度:算法完成工作最少需要多少基本操作
最坏时间复杂度:算法完成工作最多需要多少基本操作
平均时间复杂度:算法完成工作平均需要多少基本操作

算法时间复杂度计算规则：

基本操作，即只有常数项，认为其时间复杂度为O(1),
顺序结构，时间复杂度按加法进行计算
循环结构，时间复杂度按乘法进行计算
分支结构，时间复杂度取最大值
判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

算法的空间复杂度计算规则：

空间复杂度的概念
类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
空间复杂度和时间复杂度的关系
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。大部分时间我们在完成一个程序时采用空间换时间的策略
算法的时间复杂度和空间复杂度合称为算法的复杂度。

二分查找

二分查找又称折半查找，每次查找后都会将查找范围缩小一半，必须是有序列表，有两个指针，头指针和尾指针，查找头尾的数值， 直到只剩一个数，判断是否为要找的数在不在这个数组中 是的话就记录他的位置

nums = [1,2,3,4,5,6,7,8,9,11,13,14,15,18,19,23,24,25,26,28,29,30,34,35,36,37, 39,45,47,48,56,67,78,89,90,99]
head, tail = 0, len(nums)    # 头指针和尾指针
search = int(input('请输入要查找的数字：'))

while tail - head > 1:   # 确保列表长度不为1
    mid = (tail + head) // 2      # 若头指标从0下标开始   就tail//2   取整
    # 三种情况
    if search == nums[mid]:
        ans = mid

    if search <= nums[mid]:
        tail = mid

    if search >= nums[mid]:
        head = mid

# 列表为1的时候
else:
    if search == nums[head]:
        ans = head

    else:
        ans = -1    # 设定一个值   可以做判断

print(nums[ans])