algorithm/half_search.py at master · brucelee-2020/algorithm

37 lines (31 loc) · 927 Bytes

#! /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

Provide feedback