（python）用二分查找来得到列表元素首次出现的位置，包含元素重复情况，与不存在情况

二分查找递归：寻找列表中元素首次出现的位置，元素会重复，当找不到时返回None。使用二分查找可以大量减少时间与访问列表的次数。（如果自己想这是个非常痛苦的过程，所以想给别人分享一下）

实现方法：使用函数定义。

设定默认值: l是列表，x是目标元素，i=0, k=len(l)

首先定义函数 def search (l,x,i,k)

主要的思路是先得到列表的中间位置的值再来判断目标元素的大概位置

例如：100可以分为 0-50 和 50-100。

然后递归判断，目标元素是在0-25，25-50，50-75，还是75-100。

通过不断改变中间值来慢慢靠近目标元素位置是二分查找的关键。

而列表元素可能会重复，所以当每次得到l[mid]=x时，也要继续向前找看看是否存在更前的位置

现在我们开始设计代码：

我们的目的是先用二分查找递归遍历列表，所以我们通过满足i<=len(l)-1这个条件来展开循环

注意此时k=len(l)

所以要先k = k-1

所以就是：

def search(l, x, i, k):
    k = k-1 
    ans = 0 #这是判断x是否存在于列表的关键，而且不需要再次遍历列表
    while i <= k: 
      mid = (i + k) //2 #每次循环改变中间值位置
      z = l[mid]
      if z==x:
        k = mid - 1 
        firstshow = mid #遇到x直接记录当前位置，知道循环完全结束前都会改变
        ans+=1 
      elif z> x:
        k = mid - 1 
      else:
        i = mid + 1
    if ans==0:
      return None #循环结束后，如果没有出现经过 if z==x: 说明x不存在于列表
    return firstshow #得到元素首次出现的值