arrays vs lists, binary search

[@muralidhar40]

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

[@kaunajbanerjee8526]

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

[@lucygaming9726]

Python List's are Dynamic arrays not conventional arrays. en.wikipedia.org/wiki/Dynamic_array

[@neiljohn2637]

thanks for the comment, I was confused with this

[@aurkom]

@@lucygaming9726 Like vectors in cpp?

[@lucygaming9726]

@@aurkom exactly.

[@muralidhar40]

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.

[@bBbKce]

Enlightened, Great job prof

[@arjunpukale630]

The binary search program is not working The mid condition must be checked first then empty condition then it works properly

[@abhinavtyagi1657]

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) ??

[@Jaimin_Bariya]

Jp here again [comment number 25] Thank you, Sir, :)

[@akshaypatil2943]

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))

[@rohankorale6381]

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] )" 😀

[@weirdo-beardo]

At 17:40 Shouldn't we use elif instead of only if, to recursively search in RHS part of the sequence?

[@sumedh1505]

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

[@adeelshafi]

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?

[@ziya6014]

do we need to define l and r?

[@chakradharkasturi4082]

According to python design documentation Python lists are variable length arrays. docs.python.org/2/faq/design.html

[@sumedh1505]

Q: Previous program (findpos, where we found the position) , we used "Break", cant we use "Return" instead of "Break" there... Pls do rply !

[@vijayakumarlakshmanan3948]

We can , he just did to tell what a break does in a loop

[@akhilantony3581]

how can t(1) takes only one step? pls reply

[@kaunajbanerjee8526]

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.

[@bejorrani]

def Binary(sqn, v): sqn.sort() start=0 end=len(sqn)-1 while startsqn[mid]: start=mid+1 else: end=mid returnFalse

[@shrxshth_]

BINOD