问题

查找某个值在list中的位置

解决思路

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

解决（Python）

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