wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> second largest number
        
(Message started by: davidderrick on Mar 14^th, 2010, 3:01pm)

Title: second largest number
Post by davidderrick on Mar 14^th, 2010, 3:01pm

First greater number in an array. Given a large array of positive integers,
for an arbitrary integer A, we want to know the first integer in the array
which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80

Title: Re: second largest number
Post by towr on Mar 14^th, 2010, 3:38pm

Unless the array is sorted or something, I don't see that happening. If you haven't looked at all the integers in the array, you can never be certain you're not ignoring the one that is the "next larger" one.

Title: Re: second largest number
Post by Ved on Feb 7^th, 2012, 4:23am

In that case - what is the o(n) best case solution ? just to complete this thread.

Title: Re: second largest number
Post by SMQ on Feb 7^th, 2012, 5:19am

Hmm, the topic and the question asked don't seem to have anything to do with one another. For completeness, three different answers. ;)

1) Find the second-largest element in an unsorted array in O(n)

int secondLargest(int[] arr) { if (arr.length < 2) throw new IllegalArgumentException("Too few elements"); int largest = Integer.MIN_VALUE, nextLargest = Integer.MIN_VALUE; for(int i = 0; i < arr.length; ++i) { if (arr[i] > largest) { nextLargest = largest; largest = arr[i]; } else if (arr[i] > nextLargest) { nextLargest = arr[i]; } } return nextLargest; }
2) Find the first element greater than k in an unsorted array in O(n)

int firstGreaterUnsorted(int[] arr, int k) { for(int i = 0; i < arr.length; ++i) { if (arr[i] > k) return arr[i]; } throw new IllegalArgumentException("No such element"); }
3) Fint the first element greater than k in a sorted array in O(log n)

int firstGreaterSorted(int[] arr, int k) { // binary search of increasing array int first = 0, mid = arr.length/2, last = arr.length; while (mid > first && arr[mid] != k) { if (arr[mid]) first = mid; else last = mid; mid = first + (last - first)/2; } if (arr[mid] <= k) ++mid; if (mid == arr.length) throw new IllegalArgumentException("No such element"); return arr[mid]; }
--SMQ