arrays - uniform time to access any random element, however inserting/removing takes a lotta time because the constraint that array elements should be contiguous, hence shifting op needs to be performed. linked lists eliminate the need of shifting, but increase time complexity of accessing elements. swapping elements in array is lesser time than lists
python lists are best of both the arrays and linked lists, in it they take constant time for accessing any element like arrays, but also they allow for efficient addition/removal of elements like linked lists.
In the "Lists vs Arrays" discussion, the lists being studied are not Python's lists, but what is commonly referred to as linked lists. The built-in data structure List in Python may be treated as conventional arrays (mentioned at the end). According to the Python docs, accessing an element from a list is O(1) and inserting is O(n). The link below provides a table of the time complexities of all list operations for those interested. wiki.python.org/moin/TimeComplexity
With the Binary search program it won't check the last place. For eg if it is a list with 7 elements, last index being 6, due to (l-r)==0 condition, 6th index won't be checked even if it has the desire value (v). this is will help def BinarySearchWithRange(seq,v,l,r): mid = (l+r)//2 if (r-l) ==0 and seq[mid] == v: return(True) if (r-l) ==0 and seq[mid] != v: return(False) if (seq[mid] == v): return(True) elif seq[mid] > v: return(BinarySearchWithRange(seq,v,l,mid)) else: return(BinarySearchWithRange(seq,v,mid+1,r))
correct! But I think code can be improved a bit. rather putting condition of: " seq[mid]==v " at 3 places, just put : "if r - l >= 0: " This will automatically handle the zero length case and in that case mid = r = l, so we will get answer in step : " if (v == seq[mid] )" 😀
In general, let's say that searching for an element in a list of N elements takes T(N) steps. T(1) is the time taken (no. of steps) to search for an element in a list of 1 element. So, we only need to check once. For instance, if it's the list [5] and we're looking for the number 6, we check if 6 == 5 which is not true, and we're done. Hence, we need only one step.
![FORTNITE CLASSICS IS BACK! Fortnite Item Shop [November 15th, 2024] (Fortnite Chapter 5)](http://i.ytimg.com/vi/RbQURbeFwqs/mqdefault.jpg)
arrays - uniform time to access any random element, however inserting/removing takes a lotta time because the constraint that array elements should be contiguous, hence shifting op needs to be performed. linked lists eliminate the need of shifting, but increase time complexity of accessing elements. swapping elements in array is lesser time than lists
Enlightened,
Great job prof
python lists are best of both the arrays and linked lists, in it they take constant time for accessing any element like arrays, but also they allow for efficient addition/removal of elements like linked lists.
The binary search program is not working
The mid condition must be checked first then empty condition then it works properly
Jp here again [comment number 25]
Thank you, Sir, :)
In the "Lists vs Arrays" discussion, the lists being studied are not Python's lists, but what is commonly referred to as linked lists.
The built-in data structure List in Python may be treated as conventional arrays (mentioned at the end). According to the Python docs, accessing an element from a list is O(1) and inserting is O(n).
The link below provides a table of the time complexities of all list operations for those interested.
wiki.python.org/moin/TimeComplexity
Python List's are Dynamic arrays not conventional arrays.
en.wikipedia.org/wiki/Dynamic_array
thanks for the comment, I was confused with this
@@lucygaming9726 Like vectors in cpp?
@@aurkom exactly.
At 17:50, what if we don't write return in the last two conditions and only call the function bsearch(seq, v, l, mid) ??
With the Binary search program it won't check the last place.
For eg if it is a list with 7 elements, last index being 6, due to (l-r)==0 condition, 6th index won't be checked even if it has the desire value (v).
this is will help
def BinarySearchWithRange(seq,v,l,r):
mid = (l+r)//2
if (r-l) ==0 and seq[mid] == v:
return(True)
if (r-l) ==0 and seq[mid] != v:
return(False)
if (seq[mid] == v):
return(True)
elif seq[mid] > v:
return(BinarySearchWithRange(seq,v,l,mid))
else:
return(BinarySearchWithRange(seq,v,mid+1,r))
correct!
But I think code can be improved a bit.
rather putting condition of:
" seq[mid]==v "
at 3 places, just put :
"if r - l >= 0: "
This will automatically handle the zero length case and in that case mid = r = l, so we will get answer in step :
" if (v == seq[mid] )"
😀
At 17:40
Shouldn't we use elif instead of only if, to recursively search in RHS part of the sequence?
Yes, we can use... here we can use elif in LHS part of the sequence as it is defined first. If we define RHS part first we can use elif for RHS
what is r & l in function parameters? like when we call that function in promt window of python what value we pass through in terms of r & l?
do we need to define l and r?
According to python design documentation Python lists are variable length arrays.
docs.python.org/2/faq/design.html
Q: Previous program (findpos, where we found the position) , we used "Break", cant we use "Return" instead of "Break" there... Pls do rply !
We can , he just did to tell what a break does in a loop
how can t(1) takes only one step? pls reply
In general, let's say that searching for an element in a list of N elements takes T(N) steps.
T(1) is the time taken (no. of steps) to search for an element in a list of 1 element. So, we only need to check once.
For instance, if it's the list [5] and we're looking for the number 6, we check if 6 == 5 which is not true, and we're done. Hence, we need only one step.
BINOD
def Binary(sqn, v):
sqn.sort()
start=0
end=len(sqn)-1
while startsqn[mid]:
start=mid+1
else:
end=mid
returnFalse