ThomasD
BAN USERDivide and conquer method:
1. Find the element in the array.
2. If found search for 1st and last replica in the previous interval
Worst case O(2*nlogn) = O(nlogn) -first iteration find the target-
Best case O(nlogn)
Python code
def findmax(a, i, j, x):
if a[j] == x:
return j
while i + 1 < j:
print (str(i) + " " + str(j) + " max")
m = (j + i)/2
if a[m] <= x :
i = m
else: #a[m] > x
j = m
if a[i] > x:
return i-1
else:
return i
def findmin(a, i, j, x):
if a[i] == x:
return i
while i + 1 < j:
print (str(i) + " " + str(j) + " min")
m = (j + i)/2
if a[m] < x :
i = m
else: #a[m] > x
j = m
if a[i] < x:
return i+1
else:
return i
def n_occ(a, x):
l = len(a)
i = 0
j = l - 1
while i + 1 < j:
print (str(i) + " " + str(j) + " nocc")
m = (j + i)/2
if a[m] < x :
i = m
elif a[m] > x:
j = m
else: ## a[m] == x
return (findmax(a,m,j, x) - findmin(a, i, m, x) + 1)
return 0
*logn and not nlogn
- ThomasD July 03, 2015