需求介绍

1.有dateLeft和dateRight两个txt文件

　　　　　　

　　　　dateLeft.txt　　　　　　　　　　　　　　　　　　dateRight.txt

左边的表时间比较紧凑，每秒都有；右边的表时间比较分散，间隔都是几分钟

 

2.需要从Left表中取出一行，匹配属于Right表中属于哪一行的时间范围

　　例如 2017-08-21 11:44:40.838　人为观察是更接近Right表的第二行-11:44:44:154等

　　写出程序从左边找出右边所属时间的行，然后获取它的run=?

 

3.算法实现

　　1.通过两层循环遍历匹配，算出每次匹配的时间戳之差，获取最小的作为匹配目标

　　　缺点:效率缓慢，到了后期，右表前面的数据本应该不需要再计算差值，这加大了程序的执行时间

　　　整个程序跑完用时30分钟

　　

　　2.通过折半查找去匹配时间戳之差最小的值，执行效率非常快，总用时0.3秒

　　

　　以下是二分(折半)查找用例

a=[1, 2, 3, 4, 5, 6, 8, 20, 24, 31, 35]  #-----------------递归二分查找------------------  b=10  def binarySearch(array,n,left,right):      mid=left+(right-left)/2      if(left>right):          print 'find failed'          return -1      else:          if(array[mid]>n):              return binarySearch(array, n, left, mid-1)          elif(array[mid]