Python Help There is an error in my code that I can\'t track down. I am trying t

Question

Python Help

There is an error in my code that I can't track down.

I am trying to find the smallest value in O(log n) time.

List is sorted but it may be rotated

This is what I have so far

g=[3, 4, 5, 6, 7, 8, 1, 2]
z=len(g)
mid=z//2
mid+=1
fir=0
las=z-1

def a(b):
return b-1

while (las-fir) > 2:
if g[mid+1] > g[mid]: # midfirst 5 < midnext 6
if g[fir] < g[las]: # first 5 < last 6 # [4,5,6,7]
#use first
print("seta {},{}, {}".format(fir,las, g[fir:las]))
las=mid
else: # [8,5,6,7]
fir=mid
  
print("setb {},{}, {}".format(fir,las, g[fir:las]))
  
else: # midfirst 6 > midnext 3
if g[fir] < g[las]: #first 3 < last 4 # [1,4,3,2]
las=mid-1
print("setc {},{}".format(fir,las))
else: # first 6 < las 4 [5,4,3,1]
  
fir=mid+1
print("setd {},{}, {}".format(fir,las, g[fir:las]))
mid = (fir + ((las-fir)//2))
mid+=1
print("this is fir{}, mid{}, las{}".format(fir,mid,las))
d=fir
e=las-1
print(g[d:e])
if fir==las:
print(fir)
elif g[d] < g[e]:
print(g[d])
else:
print(g[e])

Explanation / Answer

Lets start with putting line number to your code, so that i could explain problems with your code.

Problems: (explained with above values)

1. There is no need to do mid += 1 on line 4, as len() function return number of elements in array(in this case: z = 8), thus on integer division it results in 4 i.e. mid = 4th index or 5th element of array, as you do +1 in mid, it is no more in mid of array rather it points to 6th element out of 8. Similarly on line 32. No need of it. This will diviate your log(n) complexity as mid is not always in between and divide the array in to two arrays of different sizes.

2. From comments on line 24 and 27, the sample arrays you provided (as [1, 4, 3, 2]), it seems you are trying to find the mininmum element even if the list is reverse sorted and rotated. This cannot be handled by same while loop. You can only find minimum element in sorted and rotated array or minimum element in reverse sorted and rotated array, but not both together, in a single while loop.

Due to point 2 your code is producing error as it is trying to handle and solve both sorted and reverse sorted rotated array using same while loop.

I hope this solves your probem, I have written code similar to your style to find minimum element in sorted and rotated array.

Code: (with comments)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.