Implementing Minimum Number Finding Algorithm in Python
The algorithm aims to find the minimum and second minimum numbers in an array using Python. Additionally, it discusses finding the nth smallest number in an array recursively along with the running time analysis. The content includes code snippets and explanations for better understanding.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
9 2 4 10 5 Find the minimum number in the array. Find the second minimum number in the array. Implement this algorithm in python.
def ?????????(A): min = ??? .??? ?????? = ??? .??? for ? in ?????(??? ? ): if ? ? < ???: ?????? = ??? min = ?[?] elseif ? ? > ??? and ? ? < ??????: ?????? = ?[?] ?????? ?????? Running time = ?(?)
Find the ?-th smallest number in an array. Suppose we want to find the 5-th smallest number in this array. 9 2 4 13 5 15 12 3
Find the ?-th smallest number in an array. Suppose we want to find the 8-th smallest number in this array. 9 2 4 13 5 15 12 3 Recurse on the algorithm again. But now, we want to find the third smallest element in this array
Find the ?-th smallest number in an array. Suppose we want to find the 2-th smallest number in this array. 9 2 4 13 5 15 12 3 Recurse on the algorithm again. We want to find the second smallest element in this array
def ???????????(A, start, end, ?): if ??? ?????: return ?[?????] index = ?????????(?,?????,???) if ????? == ????? + ? 1: return ?[?????] elseif ????? > ????? + ? 1: return ???????????(?,?????,????? 1,?) elseif ????? < ????? + ? 1: return ???????????(?,????? + 1,???,? (????? ????? + 1)) What is the running time of this algorithm?
Assume that you are trying to find ?-th element in this array Time ? 2 ? 1 ? 1 2 3 4 5 . . . ?? ?(? 1) ?(? 2) ?(? 3) . . . 1 ?? ?+1 2
?(?) def ???????????(A, start, end, ?): if ??? ?????: return ?[?????] index = ?????????(?,?????,???) if ????? == ????? + ? 1: return ?[?????] elseif ????? > ????? + ? 1: return ???????????(?,?????,????? 1,?) elseif ????? < ????? + ? 1: return ???????????(?,????? + 1,???,? (????? ????? + 1)) ?? ? 2 ? What is the best input for this algorithm? If the pivot always magically lands in the middle.
The recurrence relation is: ? 2 ? ? = ? + ?? ? 1 = ? Similar to the recurrence relation in mergesort. Show that ? ? = ?(?) Best Case: ?(?) Worst Case: ?(?2) Average Case: ?(?)
Given an array ? and an integer ?, find if ? contains ?. A linear search over the array. Takes: ?(?) time.
Given a sorted array ? and an integer ?, find is ? contains ?. Search for 11 1 4 5 9 10 15 22 33
def ???????????(A , ?): if ??? ? == 1: if ? 0 == ?: return True else: return False ??? = ???(?)//2 if ? ??? == x: return ???? elseif A mid > x: return bi????????? (?[:??? 1],?) else: return ??????????? (?[??? + 1:],?) What is the running time of this program? An immediate problem: Slicing takes ?(?) time for an array of size ? Need to avoid it.
def ???????????(A ,start, end, ?): if ??? < ?????: return False ??? = (????? + ???)//2 if ? ??? == x: return ???? elseif A mid > x: return bi????????? (?,?????,??? 1,?) else: return ??????????? (?,??? + 1,???,?) What is the running time of this program? Informal argument: In every call to ??????????? we reduce the array by half. Number of calls is log? Time taken in each ??????????? (excluding calls) = ? Running Time. = ?(log?)
?(?) def ??????????? (A ,start, end, ?): if ??? < ?????: return False ??? = (????? + ???)//2 if ? ??? == x: return ???? elseif A mid > x: return bi????????? (?,?????,??? 1,?) else: return ??????????? (?,??? + 1,???,?) ? ? 2 ? ? 2 ? ? = ? ? 1 = ? + ? Running Time is ?(log?)
def ???????????(A ,start, end, ?): if ??? < ?????: return False ??? = (????? + ???)//2 if ? ??? == x: return ???? elseif A mid > x: return bi????????? (?,?????,??? 1,?) else: return ??????????? (?,??? + 1,???,?) Recursive def ??????????? (A ,?): ????? = 0 ??? = ???(?) 1 while ????? < = ???: ??? = (????? + ???)//2 if ? ??? == x: return ???? elseif A mid > x: ??? = ??? 1 else: ????? = ??? + 1 return False Non recursive / iterative
Given a sorted array ? of distinct numbers, find if it contains an index ? such that ? ? = ?. If yes return the index ?, else return -1. -3 -2 -1 0 1 3 6 9 ? 7 0 6 3 4 5 1 2 Linear Search Takes ?(?) time. Can you do better?
-3 -2 -1 0 1 3 6 9 ? 7 0 6 3 4 5 1 2 -3 -3 -3 -3 -3 -2 0 2 ? ? ? What is special about this array? This array is also sorted and we want to search 0 in this array.
A = [-3,-2,-1,0,1,3,5,9] ? = [] for ? ?? ????? ??? ? : ?.??????(? ? ?) ??????????? (?,0,??? ? 1,0) We are doing ? ? time to just make the array. Thus, the running time of the algorithm is ? ? . Need to directly make changed in the binary search algorithm.
def ???????????(A ,start, end, ?): if ??? < ?????: return False ??? = (????? + ???)//2 if ? ??? == x: return ???? elseif A mid > x: return bi????????? (?,?????,??? 1,?) else: return ??????????? (?,??? + 1,???,?) def ??????????? (A ,start, end, ?): if ??? < ?????: return False ??? = (????? + ???)//2 if ? ??? ?? ? == x: return ???? elseif A mid mid > x: return bi????????? (?,?????,??? 1,?) else: return ??????????? (?,??? + 1,???,?)
Given a sorted array ? and a number ?, find the first and the last index of ? in A. If ? is not in A, return - 1. -3 -2 -2 0 0 0 6 9 ? 7 0 6 3 4 5 1 2
-3 -2 -2 0 0 0 6 9 ? def ??????????? (A , ?): ????? = 0 ??? = ??? ? 1 while ????? <= ???: ??? = (????? + ???)//2 if ?[???] < ?: ????? = ??? + 1 else: ??? = ??? 1 return ????? start end start end start end Write an algorithm which will find the last occorence of ? in the array.
