Find the first occurrence of a given element in the sorted list.
Search + sorted the way to go ahead is with binary search. Binary search my default doesn't guarantee to return the first occurrence of the element in case of duplicates. So what to do? search for the element using binary search, check if the element at index-1 is equal to search element if yes rerun binary search from 0 to index-1 else we have our answer.
#-------------------------------------------------------------------------------
# Name: fristKInSortedList
# Purpose: Find the first occurace of an element in the sorted list
#
# Created: 10/09/2012
#-------------------------------------------------------------------------------
def main():
sortedlist = [1,2,3,4,5,5,5,5,5,5,6,6,6,7,8,9,9,9,11,12,12,12,12,12,12,14,14,14,15,15,15,16]
element=9
print(fristKInSortedList(sortedlist,element))
def fristKInSortedList(inlist,element):
flag = True
index = len(inlist)
if inlist[0] == element:
return 0
while flag or inlist[index-1] == element:#second part of or never executes the first time
flag = False
index = binarySearchRecursive(inlist,element,0,index-1)
if index == -1:
return index
return index
def binarySearchRecursive(slist,element,begin,end):
if len(slist) <= 0:
print("invalid list! Empty List!")
return -1
if begin > end:
return -1
mid=int((begin+end)/2)
if slist[mid] > element:
return binarySearchRecursive(slist,element,begin,mid-1)
elif slist[mid] < element:
return binarySearchRecursive(slist,element,mid+1,end)
else:
return mid
if __name__ == '__main__':
main()
No comments:
Post a Comment