### Find highest and lowest element in an array with minimum comparisons array searching noOfComparisons    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (4832)

Suppose you are given an integer array of size n . How will you find the highest and lowest elements with at most 1.5n comparisons.

## Posted Answers

 Posted: 5 years ago 0 0 Edit Iterate through the array from beginning to end and compare the pairs of numbers. Find the local minimum and local maximum which takes ($$\frac{n}{2}$$) comparisons. Find global minimum from ($$\frac{n}{2}$$) local minimums and global maximum from ($$\frac{n}{2}$$) local maximums which takes ($$\frac{n}{2}$$) comparisons each. $$\therefore$$ Total number of comparisons = $$\frac{n}{2}$$ (in Step $$1$$) + $$\frac{n}{2}$$ (Find minimum in Step $$2$$) + $$\frac{n}{2}$$ (Find maximum in Step 2 ) = 1.5n ./* Initialization */struct pair{ int minimum; int maximum;};struct pair findLowestAndHighest(int[] array){ struct pair findLowestAndHighest; int i; /* If the array has even number of elements */ /* Compare the first two elements and assign minimum and maximum */ if(array.length % 2 == 0){ if(array[0] > array[1]){ findLowestAndHighest.maximum = array[0]; findLowestAndHighest.minimum = array[1]; } else{ findLowestAndHighest.minimum = array[0]; findLowestAndHighest.maximum = array[1]; } /* Starting index */ i = 2; } /* If the array has odd number of elements */ /* Initialize the first element as minimum and maximum */ else{ findLowestAndHighest.minimum = array[0]; findLowestAndHighest.maximum = array[0]; /* Starting index */ i = 1; } /* Pick element pairwise and compare them with the recent maximum and minimum */ while(i < array.length - 1){ if(array[i] > array[i+1]){ if(array[i] > findLowestAndHighest.maximum) findLowestAndHighest.maximum = array[i]; if(array[i+1] < findLowestAndHighest.minimum) findLowestAndHighest.minimum = array[i+1]; } else{ if(array[i+1] > findLowestAndHighest.maximum) findLowestAndHighest.maximum = array[i+1]; if(array[i] < findLowestAndHighest.minimum) findLowestAndHighest.minimum = array[i]; } /* Increment index by 2 as the elements are processed pairwise */ i += 2; } return findLowestAndHighest; }
You need to Sign In to post your solution.