问题

查找某个值在list中的位置

解决思路

可以用折半查询的方法解决此问题。

解决(Python)

  1. #! /usr/bin/env python
  2. #coding:utf-8
  3. #折半查找某个元素在list中的位置
  4. def half_search(lst,value,left,right):
  5. length = len(lst)
  6. while left<right:
  7. middle =(right-left)/2
  8. if lst[middle]>value:
  9. right = middle-1
  10. elif lst[middle]<value:
  11. left = middle+1
  12. else:
  13. return middle
  14. if __name__=="__main__":
  15. lst=sorted([2,4,5,9])    #折半算法中list要进行排序
  16. length = len(lst)
  17. left =0
  18. right = length-1
  19. value =4
  20. result = half_search(lst,value,left,right)
  21. if result:
  22. print result
  23. else:
  24. print"There is no the value that you want to search."

再思考

对于上面的折半方法,在python中,可以通过一个函数实现

  1. lst = sorted([2,4,5,9])    #这里进行排序,主要是为了得到与上面方法一样的结果。事实上,list.index()可以针对任何list操作,不一定非要排序
  2. result = lst.index(4)

此外,如果遇到list中有多个相同的元素,应该如何将这些元素的位置都查询出来呢?下面的方法是用python实现。

  1. def find_value_location(lst,value):
  2. result =[i for i in range(len(lst))if value==lst[i]]
  3. return result

qiwsir#gmail.com