Print Page | Close Window

Max-Min Searh Printed From: One Stop GATE Category: GATE Technical Discussions Forum Name: GATE CS Forum Discription: General Technical Discussions, Queries, doubts etc. for GATE in CS. URL: http://forum.onestopgate.com/forum_posts.asp?TID=1094 Printed Date: 03Jul2025 at 5:26pm Topic: Max-Min Searh Posted By: gita Subject: Max-Min Searh Date Posted: 08Apr2007 at 10:33pm 4.2 Max-Min Search Max-Min search problem http://www.vyomworld.com/gate/cs/ada/4.2.asp# - Following the steps of Divide and Conquer the vector can be divided into sub-problem as shown below.               The search has now reduced to comparison of 2 numbers. The time is spent in conquering and comparing which is the major step in the algorithm.   Algorithm: Max-Min (p, q, max, min) { If (p = q) Then max = a(p) min = a(q) Else If ( p – q-1) Then If a(p) > a(q) Then max = a(p) min = a(q) Else max = a(q) min = a(p) If End Else m ¬ (p+q)/2 max-min(p,m,max1,min1) max-min(m+1,q,max2,min2) max ¬ large(max1,max2) min ¬ small(min1,min2) If End If End Algorithm End. Illustration     Consider a data set with elements {82,36,49,91,12,14,06,76,92}. Initially the max and min variables have null values. In the first call, the list is broken into two equal halves.. The list is again broken down into two. This process is continued till the length of the list is either two or one. Then the maximum and minimum values are chosen from the smallest list and these values are returned to the preceding step where the length of the list is slightly big. This process is continued till the entire list is searched. The detail description is shown in fig 4.1 click here for more details: http://www.vyomworld.com/gate/cs/ada/4.2.asp - http://www.vyomworld.com/gate/cs/ada/4.2.asp

Print Page | Close Window