half_search.py

#! /usr/bin/env python
#coding:utf-8

#折半查找某个元素在list中的位置

def half_search(lst,value,left,right):
    length = len(lst)
    while left<right:
        middle = (right-left)/2
        if lst[middle]>value:
            right = middle-1
        elif lst[middle]<value:
            left = middle+1
        else:
            return middle 

#如果该元素在list中不止一个，可以用下面方法找出所有位置分布

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


if __name__=="__main__":
    lst=sorted([2,4,4,5,9])
    length = len(lst)
    left = 0
    right = length-1
    value =4 
    result = half_search(lst,value,left,right)
    if result:
        print result
    else:
        print "There is no the value that you want to search."
    lst2=[2,4,5,4,2]
    result2 = find_value_location(lst2,4)
    print result2